DEV Community

loading...

Interview Prep: Bit Manipulation: Part III

kuddleman profile image Donny ・3 min read

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

Bitwise Manipulation Part 2

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
Enter fullscreen mode Exit fullscreen mode

Now let’s say we want to right shift this number by two places. We would write:

               a >> 2
Enter fullscreen mode Exit fullscreen mode

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    
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Discussion

pic
Editor guide