Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

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