Some bit manipulation tricks.

Basics

  • Constants

0 is 0000 ... 0000
1 is 0000 ... 0001 (all bits are 0 except the least significant one)
-1 is 1111 ... 1111 (all bits are 1)
2^n is 1 << (n - 1)

Assuming 32-bit integer:

Maximum integer is ~(1 << 31), (1 << 31) - 1, or (1 << -1) - 1.
Minimum integer is 1 << 31 or 1 << -1,

This method works with any type. e.g., maximum long could be ((long)1 << 127) - 1

  • Basic operations
x << 1                //multiply x by 2
x << 2                //multiply x by 4
x >> 2                //divide x by 4
x & (8 - 1)           //mod x by 8
(x & 1) == 0          //return true if x is even
(x ^ y) >= 0          //return true if x and y are of the same sign
(x >> 31) == 0        //return true if x is positive (assuming 32-bit integer)

Hacks

  • Find absolute value
mask = x >> 31        //assuming 32-bit integer
// mask is 0 for positive integers (all bits are 0)
// mask is -1 for negative integers (all bits are 1)
(x + mask) ^ mask     //this gives the absolute value of x
// for positive integer this essentially means "plus 0 and stay put"
// for negative integer this essentially means "minus 1 and flip all bits"

//e.g.
//using 8-bit byte as an example:

///// when x is positive
// x = 0000 1101
// mask = x >> 7 = 0000 0000
// (x + mask) ^ mask is still just x

///// when x is negative
// x = 1100 1101 (= -51)
// mask = x >> 7
//   = 1111 1111
// x + mask
//   = 1100 1100
// (x + mask) ^ mask
//   = 0011 0011 (= 51)
  • x + 1 and x - 1
-~x == x + 1          //always true
-x == ~x + 1          //always true
~-x = x - 1           //always true
~x = -x - 1
//e.g.,
// x = 0000 0011
// ~x = 1111 1100 = -x - 1
// -x = 1111 1101 = ~x + 1
// -~x = 0000 0100 = x + 1
// ~-x = 0000 0010 = x - 1

You can get -x from x this way (~x + 1) or (x ^ -1) + 1.

  • Swap two numbers without using a third variable
x = x ^ y
y = x ^ y
x = x ^ y
//x and y are now swapped
  • If x is a, set x to b; if x is b, set x to a
x = a ^ b ^ x

Bit k

//(1 << k) makes a mask with only bit k not set (rightmost is bit 0)
//e.g., (1 << 4) makes 00010000
//     ~(1 << 4) makes 11101111
//thus,
x & ~(1 << k)  //turn off bit k of x
x | (1 << k)   //turn on bit k of x
x ^ (1 << k)   //flip bit kof x
(x & (1 << k)) == 0   // return true if bit k of x is not set

Rightmost Set Bit

  • About x - 1
//x - 1 always flips all bits of x starting from its rightmost set bit.
//e.g. x = 11101100, then
// x - 1 = 11101011
//Notice how the last three bits are flipped by subtraction of 1
x & (x - 1)         //turn off the rightmost set bit
x ^ (x & (x - 1))   //find where the rightmost set bit of x is
x & -x              //same effect as above
n > 0 && (x & (x - 1)) == 0  //return true when x is a power of 2 (that means, only one single set bit)
(x & -x) == x       //same effect as above
  • Brian Kernighan’s Algorithm
//Count of number of set bit, by turning them off consecutively
public static int countSetBit(int x)
    {
        int count = 0;
        while (n != 0)
        {
            ++count;
            x = x & (x - 1);
        }
        return count;
    }

English Alphabet

  • The difference between lower- and uppercase Characters
'A' - 01000001 'a' - 01100001
'B' - 01000010 'b' - 01100010
'C' - 01000011 'c' - 01100011
...

Notice that they only differ in their third significant bit. For uppercase characters, the bit is 0, and for lowercase characters, the bit is 1.

Also, in ASCII,

' ' - 00100000
'_' - 01011111

Hence, we have:

char(c | ' ')    //Convert c to lowercase; if c is already lowercase then no effect
char(c & '_')    //Convert c to uppercase; if c is already uppercase then no effect
char(c ^ ' ')    //Invert c's case
  • Position of letter in alphabet

This will work, regardless of case:

('A' & 31) //return 1
('a' & 31) //return 1
('c' & 31) //return 3

More Resources

Interested in more bit manipulations? See here
Interested in some practices? Checkout Leetcode