Bit Tricks

Tricks? Yes, you read it right! Clever programmers always love such things. Bits have made my life so easy, that I always love to talk about them! If you are new to it or find it difficult, then don’t worry, you are at the right place! This article aims at making your journey easy with bits.

Believe me, you will definitely love this post. So let’s get started!

Bits? What are they? Well, for some people, it is 0 and 1 i.e. the binary digits. I used to feel the same until one day, one of our Professors told us that they hold a special meaning. Binary digits 0 and 1 represents two states in digital electronics. Binary 0 represents OFF state while Binary 1 represents ON state.

You might be thinking, why am I talking about electronics when this article is a programming article. Guys, genius programmers not just code, they also understand the internal working of computer system. In a computer system, everything is represented in binary format i.e. in the form of 0’s and 1’s. So now, when we store a number in computer’s memory, computer actually store the binary representation of that number. Number 5 will be stored as 101 in memory.

Let’s talk about the bit representation of few numbers:

0= 0

1= 1

2= 10

3= 11

4= 100

5= 101

6= 110

7= 111

8= 1000 and so on..

I hope you already know how to convert decimal to binary.

So moving forward, do you find any pattern or anything special?

Observations

Well if you look closely, you will notice that:

1. all the odd numbers like 1,3,5 and so on, have their last bit set. By saying last bit set, I mean that their last bit is 1.
2. all the even numbers like 0, 2, 4, 6 and so on, have their last bit unset. By saying last bit unset, I mean that their last bit is 0.
3. all the numbers that are power of 2 have only the left most bit set in their binary representation. (2= 10, 4= 100, 8= 1000).
4. if a number N is a power of two, then N-1 will have all 1’s in it’s binary representation, and the number of digits in it’s binary notation will be equal to one less than the number of digits in binary representation of N. (8=1000 and 7=111)

We can find many such observations from above but currently these much observations are enough for us to proceed further.

Now, the problem is, how to get the binary representation of a number without much effort. Well, if we want to print the binary form of a given number, we must know about something called as shifting operations. Believe me, they are harmless and they will definitely make our work easy, so it’s good to know about them!

Shifting operations are nothing special. As the name suggest they shift. Now the question is, What do they shift?! Without a doubt, they like bits as much as we like them, so, they work with the bits! They are also known by a fancy name of Bit-wise Operators, as they work bit by bit.

There are two such operators.

1. LEFT SHIFT OPERATOR, represented as <<
2. RIGHT SHIFT OPERATOR, represented as >>

You can remember them by the direction of their arrow head. Example: Arrow head of left shift operator points in left direction.

When we write:

1<<0, this means shifting of binary digit 1 by 0 positions to the left and after the operation, the result will be ‘1’

1<<1, this means shifting of binary digit 1 by 1 position to the left and after the operation, the result will be ‘10’

1<<2, this means shifting of binary digit 1 by 2 positions to the left and after operation, the result will be ‘100’

number<<1, when number = 4 in decimal and 100 in binary, this means shifting of binary representation of number left by 1 position and after the operation, the result will be ‘1000’ i.e. 8, in decimal.

Similarly, for right shifting:

1>>0, this means shifting of binary digit 1 by 0 positions to the right and after operation, the result will be ‘0’

number>>1, when number = 4 in decimal and 100 in binary, this means shifting of binary representation of number right by 1 position and after the operation, the result will be ‘10’ i.e. 2, in decimal.

So basically if I write something like this:

number<<i will mean, shifting all digits in binary representation of number left i times (or shifting number left by i positions), whereas,

number>>i will mean, shifting all digits in binary representation of number right i times (or shifting number right by i positions).

Normal left shift means, appending i number of zeros at the end of the binary representation of the number. Normal right shift means, truncating the right most bits i times from the number and adding zeros at the beginning.

One very minute observation here is, if you noticed, when we shifted number 4 left by 1 position, we got 8, i.e. the result of 4 multiplied by 2. Similarly, when we shifted number 4 right by 1 position, we got 2, i.e. exactly what we get on dividing 4 by 2.

We can therefore state that:

When we left shift a number by 1 position, we are actually multiplying the number by 2. When we right shift a number by 1 position, we are actually dividing a number by 2.

Taking it further.

Let’s say our number is 9

In binary, number will be 1001

Now, 1001<<1 = 10010, which is binary equivalent of number 18.

Again, left shift the result, 10010<<1 = 100100, which is binary equivalent of number 36.

It is same as doing double left shifting of 1001. i.e. 1001<<2 = 100100

Similarly, for right shifting, 1001>>1 = 0100, that is number 4 i.e. 9 divided by 2

1001>>2 = 10, that is number 2 i.e. 9 divided by 4

We can conclude that, if we are left shifting a number i times, it would mean, we are multiplying the number by 2, i times. Similarly, if we are right shifting a number i times, it would mean, we are dividing the number by 2, i times.

We are not done yet. We need to have the basic knowledge of few more operators. I guess, you already know about them.

1. OR (represented as | ), returns 1 if either operand is non-zero, it basically do union operation.
2. AND ( represented as & ), returns 1 if all the operands are non-zero, it basically do intersection operation.
3. XOR (represented as ^ ), returns 1 for odd number of 1’s or we can say, it returns 0 when both the operands hold the same value.

Explaining with examples, you can skip this part if you already know the working of these three operators:

A= 1001, B=0101

A | B = 1101

A & B= 0001

A ^ B= 1100

Congratulation guys! We have literally covered all the basic concepts that bit manipulation operations make use of. But wait! we aren’t done yet.

Let’s try our hands at some real world problems and understand how they can be solved using this awesome technique. Bit manipulation will turn the code shorter and our work a lot more easier.

1. Fetch the bit at position i from left in the binary representation of a number.

Let the number is 10, in decimal. 10= 1010 in binary. The bit at position 2 from right is 1, assuming that rightmost bit is at position 1. How will you do it? A naive programmer would definitely convert the number from it’s decimal form to it’s binary form and then will print the bit at the required position. While this approach will work fine for a small number, but suppose we have a very large number, say, 103076. If we start converting it from decimal to binary, it will consume a lot of time and memory! But you don’t need to worry about it. As now you are a way better programmer and know the tricks bits can do!

Remember, we discussed about shifting operators. Our approach would include doing bitwise AND between the number and 1 left shifted by given position to extract the bit at that position from the number. If we left shift 1 by 1 position, we get 10. Our given number is 1010. What if, we perform an AND operation between the number 1010 and 10.

1010 & 10 = 10

result is non-zero and this suggests that the bit at position 2 of 1010 must be non-zero because of which when we AND it with 1, we get 1 at 2nd position in the result.

if the number was 1000 and we AND it with 10, result would be 1000 & 10= 0000, clearly stating that the bit at that position 2 is unset.

To check if a bit is set or unset at a given position in a number, do this

Conclusion: If number & (1<<(position-1))!=0: bit is set

2. Toggle all the bits of a number: XOR the number with all one’s.

101101 ^ 111111 => 010010 (Remember XOR operation, it returns 1 for odd number of one’s)

Conclusion: XOR by bit 1 toggles the original bit.

3. Check if a given number is a power of 2.

Well we have already discussed it. Number is power of 2 when it’s binary representation has only one 1 and that too as the left most bit.

There is one more way we can go about it. Suppose we have to check for number 8. 8= 1000 and 8–1=7=0111

if we AND the number with number-1, we will get 0, as in the above case.

But if number=3, number-1=2

3=11 and 2=10, 11 & 10 = 10 != 0

Conclusion: Number is power of 2 if Number & (Number-1)==0

4. Given an array of numbers. Array has only one element which is alone. All other elements appear in pair. Find that one element with missing pair in O(1) extra space.

You have to store the frequency of occurrence of the elements of the array somewhere. But the constraint in the problem statement states, without using any extra space. Well, you really can’t do this without using any extra space if you don’t have the knowledge about bit manipulation operations. By the time, I think you might have guessed the bit operation that we should perform. Yes! It’s XOR.

I personally believe that, XOR is a very useful and powerful operation. You should always first think if a problem can be solved using XOR.

So, let’s see, how can XOR solve this:

A ={1, 2, 3, 1, 3}, you can see that, the answer should be 2 as it is the only element with missing pair.

1= 1, 2=10, 3=11

1 ^ 1= 0

2 ^ 2 = 10 ^10 = 00

3 ^ 3 = 11 ^ 11= 00

When we XOR an element with itself, we get 0 as a result. If we XOR all the array elements, then XOR of every duplicate pair will be zero and we will be left with the only element that appears once.

1 ^ 2 ^ 3 ^ 1 ^ 3 = (1 ^ 1) ^( 3 ^ 3) ^ 2 = 0 ^ 0 ^ 2 = 2

Conclusion: XOR of element with itself results value zero.

5. Find the number of set bits in a binary representation of a number.

First approach you can make use of is to count every set bit of the number by making use of shifting operations.

Second approach: You can solve this by using AND operation.

There is an Algorithm known as Brian Kernighan’s Algorithm. It states that if we perform AND operation of the number with number-1, we actually unset it’s rightmost bit. So keep on doing this until number becomes zero.

number = number & (number-1), till number != 0 and increment the counter at each step.

Example:

Number = 11 = 1011

Number-1=10 = 1010

count =0

Number = 1011 & 1010 => 1010 and count=1

Number =1010 & 1001 => 1000 and count=2

Number = 1000 & 0111=> 0000 and count=3

As Number is now Zero. Therefore stop.

Conclusion: number of set bits in a number: number = number & (number-1), until number becomes 0 and increment the counter at each step. Finally return the counter.

6. One more trick I found useful is, if you want to find the total number of bits in a binary representation of a number, you can simply use this formula:

number of bits = floor(log(number)/ log(2))+1

Willing people can get the details of where this formula came from on google. It’s a big topic itself.

CONGRATULATIONS!

For those who have made it till the end, you guys are GENIUS!

Guys I really hope that you find this article valuable and at least now your Bit fear is gone! If still you have any queries, you can surely discuss them with me in the comment section below.

Thanks a lot for devoting your time to this blog.

Please share it among your colleagues and clap for showing appreciation! :)