Welcome back to more work on Bit Manipulation in preparation for that big job interview you’re going for.
We’ll be pushing forward based on what we’ve talked about in my last 2 articles on bit manipulation. If this subject is new to you, go ahead and read at least the first one here:
Article I
Bitwise Manipulation Part 1
Today, we’ll look at some more interview questions that can be solved by using bit manipulation. But before we do that, we’ll just need to learn one more way of manipulating bits in addition to the ones we’ve already covered in my previous articles.
Left and Right Shift Operator in Java
The Java API gives us a left shift operator ( << ) as well as a right shift operator( >> )
Let’s see how they work:
Let’s make up a base two integer. The letters above the number are just a way to identify each component of the integer. Let's set our integer to the variable “a”:
A B C D E F
a = 1 0 1 0 1 1
Now let’s say we want to right shift this number by two places. We would write:
a >> 2
So let’s take our “hand”, place it just to the left of column “A” and shove the whole integer over to the right by 2 places. But remember, any number that gets shoved to the right of column “F” just disappears!
So here’s what we get after right shifting by 2
( a > > 2)
A B C D E F
1 0 1 0
That’s all there is to right shifting.
Now let’s retrieve our original number:
A B C D E F
a = 1 0 1 0 1 1
Let’s now shift the integer contained in variable “a” 2 places in the opposite direction to the left. We’ll write it like this:
a << 2
So again we’ll take our “hand” and place it this time just to the right of column “F” and shove the whole integer two places over to the left:
A B C D E F
a = 1 0 1 0 1 1
But this gives us empty bits in columns “E” and “F” as seen above. We’ll have to fill those columns in with zeros to get our final result below:
A B C D E F
a = 1 0 1 0 1 1 0 0
And Now for Some Cool Tricks You Can Use In Your Interview:
Right shift ( > >) is the same as dividing by 2
Let’s take a decimal number , 10. Let’s convert to to base 2:
11000
We’ll right shift binary 11000 by 1 place:
1100
Binary 1100 is decimal 12 which is half of decimal 24.
You can keep shifting one place to the right and keep on halving our number to check it out!
Set the 2 to the nth bit of integer X
This is a good one.
We’re given an binary integer, say it’s 1010;
A B C D
1 0 1 0
We’re also told our “n” is 2. That means we have to set (put a one) in column B. Why column B? In short, column B is the 2 to the “n” column. Our “n” was given as “2”. Column B is our 2 to the 2nd column:
Column D is the 2 to the 0th column or the “ones” column
Column C is the 2 to the 1st column or the “twos” column
Column B is the 2 to the 2nd column or the “fours” column
The way we’ll set our column B is by using this simple formula:
x | ( 1 << n)
Let’s work it out. First let’s start with what’s inside the parens on the right side of the bitwise “OR” operator ( | ): 1 << n
We want to shift the integer “1” to the left by n places. We were given n as “2”. Let’s do it:
1 //original integer
1 0 0 // shift the original
over to the left by
2 places
Now let compare our x, 1010, to 100 using bitwise OR ( | )
A B C D
1 0 1 0
0 1 0 0
_____________
1 1 1 0 // 1010 | 0100
After applying bitwise OR, we see that in our result ( 1 1 1 0 ), in column B is now set as the problem required.
These are just two of the very fun things you can do with bit manipulation. I hope it’s whetted your appetite for more. Using base 2 and bit manipulation allows for a fine tuning of our integers that would be clunky in base ten.
Keep on coding out your dreams!
Namaste
Top comments (0)