C, 134

The C preprocessor is pretty fun to abuse. Basically this macro defines the 3 functions, a, o, and x, for and, or, and xor respectively. The only difference in the algorithm for these operations is the criteria for setting the bit in the result.

not is the function n.

#define f(n,c)n(a,b){for(r=0,i=31;i+1;--i)if(((a>>i)%2+(b>>i)%2)c)r+=1<<i;return r;} i,r;n(a){return 0xffffffff-a;}f(a,/2)f(o,)f(x,%2) 

Tester program (takes a long time, I didn't spend any time optimizing it at all, but it does test every test case possible, beside MAX_INT related ones):

#define m_assert(expected, condition, actual)\ if(!((expected) condition (actual)))\ printf("assert fail @ line %i, expected: %x, actual %x, condition "#condition"\n", __LINE__, expected, actual); int main() { unsigned int j,k; for(j=0; j<0xffff; ++j) { m_assert(~j, ==, n(j)); for(k=0; k<0xffff; ++k) { m_assert(j & k, ==, a(j,k)); m_assert(j | k, ==, o(j,k)); m_assert(j ^ k, ==, x(j,k)); } } 

ised 76 bytes

ised also doesn't have bitwise operations - usually annoying, but now welcome, because we really need to implement them.

Functions will be stored in numbered memory slots (no verbose names).

Conversion to and from binary:

@5{:x/2^[32]%2:}; @6{:x@:2^[32]:}; 

NOT could be @1{:$6::{1-$5::x}:} but it's obviously easier to just subtract:

@1{:2^32-x-1:}; 

OR:

@2{:$6::{$5::{x_0}:+$5::{x_1}>0}:}; 

AND:

@3{:$6::{$5::{x_0}:*$5::{x_1}}:}; 

XOR:

@4{:$6::{$5::{x_0}:<>$5::{x_1}}:}; 

This would bring us to 156 bytes (with newlines and semicolons). A test code would just be (NOT, OR, AND, XOR in succession, found under names $1,$2,$3,$4):

> $1::{6} 4294967289 > $2::{12 11} 15 > $3::{12 11} 8 > $4::{12 11} 7 

But of course OR and NOT are all we really need and things can be simplified:

@1{:2^32-x-1:}; @2{:@+{2^U{?{$5::x}%32}}:}; @3{:${1 2 1}::x:}; @4{:$3::{$2::x${1 2}::x}:}; @5{:x/2^[32]%2:}; 

That's 109 characters. When newlines and semicolons are skipped, and with a bit more golfing, we have 76 characters:

@3{@1{:2^32-x-1:}@2{:@+{2^U{?{x/2^[32]%2}%32}}:}$1}@4{{:$2::x${1 2}::x:}$3}; 

Nim (537)(490)

Nim Compiler 0.10.2

I've been looking for a reason to learn nim so here we go.

For code golf, I have leveraged variable parameters and implicit returns. The variable parameters, per the documentation are less stack efficient. Personally, I find the implicit returns harder to read and would probably only use them in trivial procedures.

As for the algorithms, they are simple enough. For all operations except NOT, we compare each bit and manually compare them to our expected truth table. Set each bit as needed along the way in our output variable. In Nim, result is the implicit return value.

I wasn't sure if we were allowed to use built-in OR and AND for asserting two boolean conditions so the notZero procedure was put in their place.

proc s(x, y, b: var int)= x = x div 2 y = y div 2 b *= 2 proc n(x: var int): int = return -(x+1) proc a(x, y: var int): int = var b = 1 while x > 0 and y > 0: if (x mod 2 + y mod 2) == 2: result += b s(x,y,b) proc o(x, y: var int): int = var b = 1 while x + y > 0: if (x mod 2 + y mod 2) >= 1: result += b s(x,y,b) proc r(x, y: var int): int = var b = 1 while x + y > 0: if (x mod 2 + y mod 2) == 1: result += b s(x,y,b) 

Still looking for a better method...

Here is the non-squished version plus full test harness to run on your own machine.
If you just want to run a couple of inputs, here is test case lite.

CJam, 71 bytes

{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X]; 

Explanation

"B : UInt64 UInt64 String -> UInt64 Computes a bitwise operation on the two given unsigned integers. The operation is defined by the logical inverse of the result of evaluating the given string given the sum of two input bits."; { :F; "Save the operation string."; 0 "Initialize the result to 0."; { "For I from 0 through 63:"; :R; "Save the result."; 2md@2md@ "Divide each input by 2 and collect the remainders as the next pair of bits to process."; +F~! "Compute the logical inverse of the result of evaluating the operation string given the sum of the two bits."; 2I#* "Adjust the resulting bit to be in the correct output position by multiplying it by 2^I."; R+ "Add the location-adjusted bit to the result."; }64fI \;\; "Clean up."; }:B "A : UInt64 UInt64 -> UInt64 Computes the bitwise AND of the two given unsigned integers. This is done by passing the inputs along to B with an operation such that: bit_out = !((bit_in_1 + bit_in_2) - 2)"; {"2-"B}:A "O : UInt64 UInt64 -> UInt64 Computes the bitwise OR of the two given unsigned integers. This is done by passing the inputs along to B with an operation such that: bit_out = !(!(bit_in_1 + bit_in_2))"; {'!B}:O "N : UInt64 -> UInt64 Computes the bitwise NOT of the given unsigned integer. This is done by passing the input and 0 along to B with an operation such that: bit_out = !((bit_in + 0))"; {0SB}:N "X : UInt64 UInt64 -> UInt64 Computes the bitwise XOR of the two given unsigned integers. This is done by passing the inputs along to B with an operation such that: bit_out = !((bit_in_1 + bit_in_2) - 1)"; {'(B}:X ]; "Clean up."; 

Test suite

This code tests runs of each of my and, or, not, and xor functions 100 times with uniformly-distributed 64-bit unsigned inputs and compares the result with that produced by the built-in operator. Due to gratuitous use of the eval operator, it's quite slow and may take up to about a minute with the online interpreter. But if all goes well, execution should end with no output, because any discrepancies found are printed.

N:L; {:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X]; {;Y32#__mr*\mr+}2e2%2/{~:U;:V;"A&O|X^"2/{[{US@SV" = "UV5$~L}/9$2$={];}{]oLo}?}/"N~"[{U" = "U3$~Y64#(&L}/6$2$={];}{]oLo}?}/ 

JavaScript 294 267

Was able to shave off a few more bytes with @AlexA.'s and @kennytm's suggestions.

Functions:

B=(n,m,t)=>{for(var p=4294967296,y=0;p>=1;p/=2)y+=t=='x'&&(n>=p||m>=p)&& !(n>=p&&m>=p)?p:0,y+=t=='a'&&n>=p&&m>=p?p:0,y+=t=='o'&&(n>=p||m>=p)?p:0,n-=n>=p?p:0,m-=m>=p?p:0 return y} N=(n)=>{return 4294967295-n} A=(n,m)=>B(n,m,'a') O=(n,m)=>B(n,m,'o') X=(n,m)=>B(n,m,'x') 

example:

var n = 300; var m = 256; console.log(X(n,m) + ", " + (n ^ m)); console.log(O(n,m) + ", " + (n | m)); console.log(A(n,m) + ", " + (n & m)); console.log(N(n) + ", " + (~n>>>0)); console.log(N(m) + ", " + (~m>>>0)); 

output:

44, 44 300, 300 256, 256 4294966995, 4294966995 4294967039, 4294967039