Program that prints itself
main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

Turn off rightmost 1-bit (use to get power of 2)
x & (x-1)

Test if of the form 2^n-1
x & (x+1)

Isolate rightmost 1-bit
x & (-x)

Isolate rightmost 0-bit
~x & (x+1)

Create a mask identifying trailing 0s
~x & (x-1)

Propagate rightmost 1-bit
x | (x-1)

Turn off rightmost contiguous string of 1-bits
((x | (x-1))+1) & x

Theorem. A function mapping words to words can be implemented with add, subtract,
and, or, not iff each bit of result depends only on bits at and to the right of
each input operand
Hence. No sequence of instructions turning off leftmost 1-bit in a word

Find next higher number that has same number of 1-bits
a = Isolate rightmost 1-bit of x
b = a + x
c = b ^ x
c = (c >> 2)/a
return b | c

x + y = (x ^ y) + 2(x & y) = (x | y) + (x & y)
x ^ y = (x | y) - (x & y)
-~x = x+1
~-x = x-1
x | y = (x & ~y) + y
x & y = (~x | y) - ~x
x == y = (x & y) - (x | y) - 1

abs(x)
y = x>>31 (signed)
(x ^ y) - y,   or
(x + y) ^ y

Sign Extension
((x ^ 0x00000080) & 0x000000FF) - 0x00000080

Signum
(x >>s 31) | (-x >>u 31)   or
-(x >>u 31) | (-x >>u 31)

x < y
(x-y) ^ ((x^y) & ((x-y) ^ x))

x > 0
-x & ~x

Multiword add
s = (x & 0x7f7f7f7f) + (y & 0x7f7f7f7f)
s = ((x^y) & 0x80808080) ^ s

Multiword subtract
d = (x | 0x80808080) - (y & 0x7f7f7f7f)
d = ((x^y) | 0x7f7f7f7f)==d

Exchanging registers
x = x^y
y = y^x
x = x^y

Exchange contents of two registers wherever mask bit=0, leave otherwise
x = x^y
y = y^(x&m)
x = x^y

Alternate between two values, x = (x==a) ? b : a
x = a^b^x

Round down to next smaller multiple of 8
x & -8

Round up
(x+7) & -8

Round down to nearest power of 2
x = x | (x >> 1)
x = x | (x >> 2)
x = x | (x >> 4)
x = x | (x >> 8)
x = x | (x >> 16)
return x - (x >> 1)

Round up
x = x - 1;
x = x | (x >> 1)
x = x | (x >> 2)
x = x | (x >> 4)
x = x | (x >> 8)
x = x | (x >> 16)
return x+1

population count (# of 1-bits in a word)
0 0 1 0 1 1 0 1, add each 2-bit field
0 0|0 1|1 0|0 1 i.e.  0 | 1 | 2 | 1
0 0 0 1|0 0 1 1 i.e.      1 |     3
0 0 0 0 0 1 0 0
x = (x & 0x55555555) + ((x >> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f)
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff)
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff)
simplify to
x = x - ((x >> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003f

pop(x) = x - floor(x/2) - floor(x/4) - ... - floor(x/2^31)
pop(x) = - sum_0^31 (x <<rot i)

parity
y = x ^ (x >> 1)
y = y ^ (y >> 2)
y = y ^ (y >> 4)
y = y ^ (y >> 8)
y = y ^ (y >> 16)
rightmost bit of y

nlz
if(x==0) return 32
n = 1
if((x >> 16)==0) {n = n+16; x = x<<16;}
if((x >> 24)==0) {n = n+8; x = x<<8;}
if((x >> 28)==0) {n = n+4; x = x<<4;}
if((x >> 30)==0) {n = n+2; x = x<<2;}
n = n - (x>>31)
return n
used to generate Exp() distributed variables -- generate uniform integers, take nlz

reversing bits
x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;

swap left and right half of register
x = (x >> 16) | (x << 16)

divide n by 3
M = 0x55555556
q = high word of (M*n)
if(n<0) ++q
r = n - q*3

divide n by 5
M = 0x66666667
q = high word of (M*n)
q = q >>s 1
if(n<0) ++q
r = n - q*5

divide n by 7
M = 0x92492493
q = high word of M*n  + n
q = q >>s 2
if(n<0) ++q
r = n - q*7

Using -2 as the base
Using i-1 as the base
2 = 1100

Hilbert Curve

 |--|
 |  |

 --| |--
 | |-| |
 |     |
 --| |--
 --| |--