Bit manipulation

Bit manipulation is important part of competitive programming and is needed to solve a variety of problems.

Bitwise Operators

To understand bit manipulation you need to know what bitwise operators are and how they work.

There are 6 types of bitwise operators:

• and (&)
  • Here each bit is multiplied
  • 1 * 1 = 1
  • 1 * 0 = 0
  • 0 * 0 = 0
  • 0 * 1 = 0
  • example: 1001 & 1100 = 1000
• or (|)
  • Each bit is added with other
  • 1 + 1 = 1
  • 1 + 0 = 1
  • 0 + 1 = 1
  • 0 + 0 = 0
  • example: 1001 | 1100 = 1101
• xor (^)
  • If same then 0, if different then 1
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0
  • 0 ^ 0 = 0
  • 0 ^ 1 = 1
  • example: 1001 ^ 1100 = 0101
• complement (~)
  • Inverts all bits of binary representation
  • example : 0101 = 1010
• left shift (<<)
  • Shifts the value to the left in binary representation
  • example: 0011 << 1 = 0110
  • here the represenation is shifted towards left by 1
• right shift (>>)
  • Shifts the value to the right in binary representation
  • example: 1100 >> 1 = 0110
  • here the represenation is shifted towards right by 1

Complement is probably the most least used bitwise operator.

Important note - To just clear the confusion I m using end and start like this - forEx(0001) 1 is at the end and 0 is at the start.

• In binary form of any number every

  • even number ends with 0
  • odd number ends with 1
  • power of 2 has only 1 bit. For ex - 16 = 10000

• Divide by 2 operation is similar to right shift by 1.

  • (14 / 2 = 7 is same as 14(1110) >> 1 = 0111. Here 0111 == 7)

• Power Operation

  • Power of 2 (1 << x)

• Xor Operation

  • a ^ b = c, c ^ a = b, c ^ b = a

Some popular tricks

1. To Set a bit at position n simply do (x |= (1 << n)).
   • You left shift 1 at position n and then add it x basically making that place also set (1).
2. To Check a bit at any position n in number x do (1 & (x >> n)).
   • To see how this is working let's take a example where x = 9 and n = 3.
   • Binary of 9 - 1001.
   • Right shifting 1001 3 times will result in 0001.
   • As you can see that the bit that we wanted to check i.e the one at third position is now in the end.
   • So now just simply multiply it with 1 binary (0001) will result in 1.
   • So we can conclude that bit at 3rd position in 9 is set(1).
   • As you can see the multiply by 1 is what set's the bit we want apart from others. If bit that we want is set than it will result in 1 as in above example otherwise 0.
3. One More way to do above point 2 is (x & (1 << n)). But it doesn't return 1 or 0, so it can only be used in conditionals. Be careful while using it for something else.
4. To unset (0) the last bit (first from right) of any number x do (x & (x - 1)).
   • x - 1 will make just last bit 0 and then multiply it with original number i.e. x in this case.
   • Some other ways -
     • x - (x & - x)
     • x ^ (x & (~x + 1))
5. Flip a bit any position n in number x using x ^ (1 << n).
6. In C/C++ you can find 2's complement of any decimal number x just by implicitly casting it to unsigned int.
   • unsigned int twosComplement = x;
7. Also 2's complement of any number x can be found just by -x. Simple as that.
   • Refer to this stackoverflow article for explanation. Link.
   • From the same article - To get the lowest set bit just do x & -x.
8. To Convert a character to lowercase or uppercase using bitwise operator
   • To convert to upper case - c & (~32).
   • To convert to lower case - c | (32).
   • To simply toggle case whether it's lower to upper or vice versa - c ^ 32
   • Here c is some character. If c is digit it will throw garbage values.
9. To get the last set bit (first from right side) do x & -x.

Number of bit flips to convert A to B -> (0 to 1) or (1 to 0)

Let two number be a and b.
If you take XOR of a and b and then count number of 1's in it. You will get minimum number of conversions to convert a to b.

Reason being is to convert the number a to b you have to find the positons at which A and B differs and you can do that by taking XOR.
For example convert 10 to 7.

• Binary Form of 10 is 1010 and 7 is 0111
• XOR of both 10 and 7 is 1101.
• Number of 1 in 1101 is 3. Hence answer is 3.
• You need to flip 3 bits to convert 10 to 7.

This example is from question 2220. Minimum Bit Flips to Convert Number.

1863. Sum of XOR Of all Subsets of a Array

We have to find the sum of xor of all the subsets.
So instead of generating all subsets We can find the total number of subsets as 2 power size_of_array. In bit it can be done as (1 << size_of_array).
The way we are getting all subsets is -

• Consider a array of 3 elements [5, 6, 1]

• If you will do 2 power 3 (here 3 is size of array) you will get 8. There are 8 possible subsets.

• Now i am pretty sure u can guess what those will be

  
  

  000
  001
  010
  011
  100
  101
  110
  111

• The way it will help to consider all subsets is whenever there is 1 we will consider the element at that position to exist, and whenever 0 we will not consider it.

  • For example lets take 011
  • Because in 011 element at both index 0 and 1 is 1.
  • Now we have just have to take XOR of element at index 0 and 1 from array. In array index 0 is 5 and index 1 is 6. We are taking XOR since that's what we were asked to do in the question.
  • Now just add this XOR to the total SUM.

int subsetXORSum(vector<int> &v)
{
    int ans = 0;
    for(int i = 0; i < (1 << v.size()); i++)
    {
        int x = 0;
        for(int j = 0; j < v.size(); ++j)
            if(i & (1 << j))
                x ^= v[j];
        ans += x;
    }
    return ans;
}

There's a way to do this in O(N) time complexity but the problem is that I do not understand how @vortubac reached to that conclusion. But the code is pretty simple. Check his post here.

Note

I will keep updating this article as I will find something interesting. If you find something wrong feel free to mention it in comment section.