hyfr!

Bitwise operators and tricks!

December 31, 2018 • ☕️☕️ 8 min read

Bit operations operate on the individual bits of the bit patterns and we perform such operations using bitwise operators. Data in memory (RAM) is organized as a sequence of bytes. Each byte is a group of eight consecutive bits. We use bitwise operators whenever we need to manipulate bits directly. Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level. Bitwise operators are language agnostic and getting hold of them can help in doing some things easily and most importantly in a shorter and sharper way.

Bitwise Operators:-

NOT (~ or !) :

  • How it works
A !A
0 1
1 0


  • Bitwise NOT is simply the 1s complement of a number.
  • Unary operator.

AND ( & ):

  • How it works
A B A&B
0 0 0
0 1 0
1 0 0
1 1 1
  • Operates on two equal-length bit patterns, !(works on 1100 and 00)
  • Binary operator.

OR ( | ):

  • How it works
A B A|B
0 0 0
0 1 1
1 0 1
1 1 1
  • Operates on two equal-length bit patterns, !(works on 1100 and 00)
  • Binary operator.

XOR ( ^ ):

  • How it works
A B A^B
0 0 0
0 1 1
1 0 1
1 1 0
  • Returns 1 only if exactly one bit is set to 1 out of the two bits in comparison.
  • Operates on two equal-length bit patterns, !(works on 1100 and 00)
  • Binary operator.

Left Shift ( << ):

  • How it works

    • Shift n number of bits to the left and append 0 at the end.
  • Using this operator is equivalent to multiplying the bit pattern with 2 n ( if we are shifting n bits ) i.e.

    • 1 << 1 (shift 1 bit so 21 = 2) = 2
    • 1 << 2 (shift 2 bit so 22 = 4)= 4
    • 1 << 3 = 8
  • 419 in binary 0000111110110011 << 1 = 838 (0001111101100110)

Right Shift( >> ):

  • How it works

    • Shift n of bits to the right and append 1 at the end.
  • Using this operator is equivalent to dividing the bit pattern by 2 n ( if we are shifting n bits ) i.e.

    • 4 >> 1(shift 1 bit so 21 = 2) = 2
    • 6 >> 1 = 3
  • 220 in binary 11011100 >> 1 = 110 (1101110)

    • 221 in binary 11011101 >> 1 = same ans 110(1101110)

Observations (will help in getting hold of tricks better)

  • Difference between a binary number n and n-1 is : All the bits on the right of the rightmost 1 are flipped including the rightmost 1(which will get zero). Some examples :

    • 1000 (8) -flips-> 0111 (7)
    • 0111 (7) -flips-> 0110 (rightmost 1 only got flipped, didn’t had any more towards right)
  • If 12 (1100) then -12 in binary representation will be 2’s complement of (1100) i.e 1’s complement(1100) + 1 = 0100, We traverse the one’s complement starting from right most bit towards left , and look for 0. We flip all 1’s to 0 until we find a 0. Finally, we flip the found 0

  • Two unique properties of XOR

    • n ^ n = 0

    • n ^ 0 = n

Application & Tricks (Fun part!)

  • Fenwick Tree or Binary Indexed tree

    • Helps in calculating prefix sums in an array efficiently. For example, an array is [100, -100, -1, 1, 12] the length 3 prefix [100, -100, -1] with sum 100 - 100 + -1 = -1). If you are into competitve programming or have given long contest on codechef then 4/5 th question generally requires you to do things like

      • Point update operation : Update the value stored at an index i.
      • Range sum query : Find the sum of a prefix of length k.
    • Similar Data structure called Segment Trees also can be used to do things above mentioned but Fenwick tree code is much short, easier to understand and memory efficient on other side in a segment tree solution there exists a lot of boilerplate code. Also both DS take O(logN) time.
  • Prerequisite for fenwick trees : How to get last set bit ? For example For 1010, you should perform some operations to give 0010 as the output where 1 is last set bit in 1010. For this solution is just this simple equation x ^ (x & (x - 1)) (See how sharp bitwise solutions are!)..Lets make truth table of this to get how this equation works:

x(8) x-1(7) x & x-1 = mans x ^ mans
1 1 1 0
1 0 0 1 last set bit
0 1 0 0
0 1 0 0
  • (x & (x - 1)) this equation actually came from our observation defined in above section. XOR(^) helps in removing 1 which exists in both results so we get last set bit!

  • We can use above equation and fenwick tree to maintain a partial sum tree(array to be precise). Denote BIT[] as fenwick tree and any index we can store sum of some numbers of any given array.

For every index i in the BIT[] array we store the cumulative sum from the index i to i - (1<<r) + 1 (both inclusive), where r represents the last set bit in the index i. So in mathematical equation this means

            {   
                a[1] + ... + a[x],     if x is power of 2
BIT[x] =                
                a[x],                  if x is odd
            }
  • How (x & (x - 1)) equation played a role in above fenwick equation?

    • If we see numbers 2,4,8.. in binary form 0010,0100,1000..so on then we always get a last set bit with no other set bits(1 bit) in the representation so if r represents set bit position ex: For 4 (0100) set bit position is 3(0 for 0 ,0 for 1, 1 for 2 if read from right -> left) so

    • if i = 4 then range [i to i - (1<<r) + 1] represents 4 to 4 - (2 r = 2 2 = 4) + 1 = [4,1] i.e index 4 should contain sum of first 4 elements.

    • if i = 16 then 16(10000)-(2 r = 2 4 = 16 - 16 + 1 = 1) i.e index 16 should contain sum of first 16 elements.

    • if i = 3 then 3(0011) - (2 r = 2 0 = 1 = 3-1+1) = [3,3] i.e index 3 will contain sum of only number at index 3 or just value at index 3.

  • Brian Kernighan’s Algorithm

    • It helps in finding no of set bits(1s) in binary representation of a number.
    • Again using our observation about x & x-1 and use it to give rightmost set bit so if we do it again and again till we get 0 then we will get no of set bits it originally had! This is what Brian Kernighan’s algo does.

      while (n) {
      n = n & (n-1);
      count++; 
      }
  • Get non-repeated value from array of duplicates

    • Example array [1, 33, 54, 4, 7, 8, 8901, 33, 1, 4, 54, 8, 8901] and answer will be 7 if we use XOR operation by using its property of m ^ m = 0 && m ^ 0 = m.

    • Manually lets XOR one by one and also take XOR of 7 at last so that before that we should have something like 0000 then only this property 0^7 would give us the answer.

      1 ^ 33
          1	00000001
      ^	33	00100001
      =	32	00100000
      
      32	00100000
      ^	54	00110110
      =	22	00010110
      
      22 ^ 4
          22	00010110
      ^	4	00000100
      =	18	00010010
      
      18 ^ 8
          18	00010010
      ^	8	00001000
      =	26	00011010
      
      26 ^ 8901
          26	    0000000000011010
      ^	8901	0010001011000101
      =	8927	0010001011011111
      
      8927 ^ 33
          8927	0010001011011111
      ^	33	    0000000000100001
      =	8958	0010001011111110
      
      8958 ^ 1
          8958	0010001011111110
      ^	1	    0000000000000001
      =	8959	0010001011111111
      
      8959 ^ 4
          8959	0010001011111111
      ^	4	    0000000000000100
      =	8955	0010001011111011
      
      8955 ^ 54
          8955	0010001011111011
      ^	54	    0000000000110110
      =	8909	0010001011001101
      
      8909 ^ 8
          8909	0010001011001101
      ^   8	    0000000000001000
      =	8901	0010001011000101
      
      8901 ^ 8901
          8901	0010001011000101
      ^	8901	0010001011000101
      =	0	0000000000000000 (Here we go!)
      
      0 ^ 7
          0	00000000
      ^	7	00000111
      =	7	00000111 Finally :)
  • Checking if given 32 bit integer is power of 2

    • All the power of 2 have only single bit set and using our x and x-1 observation if we perform (x & x-1) then if x is power of 2 this will give 0 otherwise 1. So !(x & x-1) will give whether the number is power of 2. If case of x = 0 we dont wish to do x-1 so final equation is

      (x && !(x & x-1))

  • Quick conditional assignment

    • We as programmers write below code block a lot times (literally a lot!)
       if (x == a)
          x = b;
       if (x == b)
          x = a;

    Better way

       x = a ^ b ^ x 
  • If a number is even or odd

    • Binary representation of a even number has no set bit at right most or LSB postion but odd number does so we can check like
       if x & 1
          fmt.Println("ODD")
       else
          fmt.Println("EVEN")
  • Swap numbers without extra variables

    • Using XOR we can do this for example :- Swapping i with k and viceversa.
        i = i ^ k; // i has both i and k let it be I
        k = i ^ k; // remove k from I so k = i
        i = i ^ k; // remove k (which is now i) from I so i = k

I also wanted to explain how bitwise operators are related to set theory but for now keeping this post short and sweet we will be covering this topic into a separate article along with some interesting problems on algorithms, data structures and tricks explained above.

Thanks! 🙌

The fault in my articles, they don't close themselves.

Discuss on Twitter