Bit Hacks

Question 1

x AND 0’s

Answer 1

0

Question 2

x AND 1’s

Answer 2

x

Question 3

x AND x

Answer 3

x

Question 4

x OR 0’s

Answer 4

x

Question 5

x OR 1’s

Answer 5

1’s

Question 6

x OR x

Answer 6

x

Question 7

x XOR 0’s

Answer 7

x

Question 8

x XOR 1’s

Answer 8

~x

Question 9

x XOR x

Answer 9

0’s

Question 10

checking if the kth bit is set

Answer 10

n AND (1

Question 11

setting the kth bit

Answer 11

n OR (1

Question 12

clearing the kth bit

Answer 12

n AND ~(1

Question 13

toggling kth bit

Answer 13

n XOR (1

Question 14

toggling rightmost one bit

Answer 14

n AND n-1

Question 15

isolating rightmost one bit

Answer 15

n AND -n

Question 16

isolating rightmost zero bit

Answer 16

~n AND n+1

Question 17

checking where number is a power of 2

Answer 17

(n AND n-1) == 0

Question 18

multiplying by a power of 2 (2^k)

Answer 18

n

Question 19

dividing by a power of 2 (2^k)

Answer 19

n&raquo_space; K

Question 20

finding the modulo of a given number

Answer 20

n AND 0x[hex value]

Question 21

creating mask for trailing zeros

Answer 21

(n AND -n) - 1

Question 22

reversing a binary number

Answer 22

unsigned int n, nReverse = n;
int s = sizeof(n);
for( ; n; n >>=1)
    nReverse |= n AND 1
    s--;
nReverse

Question 23

swap all odd and even bits

Answer 23

find even bits in N (evenN) = n AND 0xAA
find odd bits in N (oddN) = n AND 0x55
evenN&raquo_space;= 1
oddN

Question 24

check if 1 ints are equal WITHOUT comparison operators

Answer 24

!( i ^ j )

Question 25

detect if 2 ints have opposite signs

Answer 25

bool f = ((x^y)

Question 26

compute min of 2 ints, x and y

Answer 26

r = y XOR ((x XOR y) AND -(x

Question 27

compute max of 2 ints, x and y

Answer 27

r = x XOR ((x XOR y) AND -(x

Question 28

counting bits set - naive way

Answer 28

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

for (c = 0; v; v&raquo_space;= 1){
c += v AND 1;
}

Question 29

swapping values with XOR

Answer 29

define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))