Show Menu
Cheatography

Bit Hacks Cheat Sheet (DRAFT) by

When dealing with software close to hardware, these bit hacks might come in handy. From setting and getting to parity and calculations.

This is a draft cheat sheet. It is a work in progress and is not finished yet.

C/C++ bitwise operations

&
AND
|
OR
^
XOR
~
NOT
<<
SHIFT (left)
>>
SHIFT (right)

Useful snippets

Counting (c) bits set in x
for (c = 0; x; c++) {  x &= vx- 1;  }
Computing parity in parallel (32 Bit)
x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x &= 0xf; return (0x6996 >> x) & 1;
 

Integer arithm­etics

x = y << n
Multiply by n times 2
x = y >> n
Divide by n times 2
return (x & 1) == 0
Is x even?
return (x && !(x & (x - 1)))
Is x power of 2?
return (x ^ y) < 0
Has x opposite sign than y?
y ^ ((x ^ y) & -(x < y))
min(x,y)
x ^ ((x ^ y) & -(x < y))
max(x,y)
 

Single bit operations

y = x | (1<­<n)
Set the nth bit
y = x & ~(1<<n)
Unset the nth bit
y = x ^ (1<­<n)
Toggle the nth bit
return x & (1<­<n)
Test if the nth bit is set
y = x & (x-1)
Turn off rightmost 1bit
y = x & (-x)
Isolate rightmost 1bit
y = x | (x-1)
Right propagate rightmost 1bit (fill in ones)
y = x | (x+1)
Turn on rightmost 0bit
y = ~x & (x+1)
Isolate rightmost 0bit