Bit Manipulation

What is a bit?

A bit is a binary digit. It is the smallest unit of data in a computer with a value of 0 or 1.

Example :

34 in binary is 100010

What is bit manipulation?

This is the process of applying logical operations to a sequence of bits to get the solution in an optimized way.

BITWISE OPERAT0RS

Bitwise Operators

A | B (OR)

When we compare two booleans, we normally do firstboolean || secondboolean. That expression is true if one or both booleans are true. The | operator compares each binary digit across two integers and gives back a 1 if either of the integers is 1 or both are 1.

A & B (AND)

The & operator only outputs a 1 when both binary digits of our two integers are 1. Again, this is similar to the && operator with booleans.

A^B (XOR)

It compares the binary digits of these numbers. If only one of the integers is a 1, it will insert a 1 into the result, otherwise, it will insert a 0 hence the name XOR, or “exclusive or”.

~A (NOT)

Instead of taking an integer on each side of it, it takes an integer only after it. Just as! flips a boolean from true to false or false to true, the ~ operator reverses each binary digit in an integer: from 0 to 1 or 1 to 0.

MORE BITWISE OPERAT0RS…

The << Operator (LEFT SHIFT)

This operator shifts an integer. On the left side of the operator is the integer that is being shifted, and on the right is how much to shift by.

Example :

We’re just going to pretend integers only have 8 bits instead of 32. You can refer to the 8-bit binary conversion table here

Working with decimals

Here we have the number 34 sitting on its nice block of memory 8 bits wide.

34 << 2 is shifting the number 34 to the left by 2 places.

But what do we do with the 2 open bits of memory where we moved the digits from?

Any empty spots are just replaced with 0s. We end up with 10001000 according to this table is 136.

                            34 << 2 is 136

The >>Operator (RIGHT SHIFT)

Here, everything slides to the right the amount we specify. The only slight difference is what the empty bits get filled with.

If the integer is starting with a negative number (a binary number where the leftmost bit is a 1), all the empty spaces are filled with a 1. If we’re starting with a positive number (where the leftmost bit, or most significant bit, is a 0), then all the empty spaces are filled with a 0.

While this sounds complicated, it basically just preserves the sign of the number we start with. So -3 >> 2 == -12 while 3 >> 2 == 12.

Example :

We can refer to this Decimal Binary Conversion Table as we are still working with 8 bits

Working with hexadecimal

Here we have the hexadecimal 0x89 sitting on its nice block of memory 8 bits wide.

0x89 >> 3 is shifting 0x89(a hexadecimal) to the right by 3 places

Now let’s fix the 3 open bits of memory where we moved the digits from, as we have a positive number (where the leftmost bit, or most significant bit, is a 0), then all the empty spaces are filled with a 0.

We end up with 000 10001 which according to this Decimal Binary Conversion Table is 0x11.

                           0x89 >> 3 is 0x11

CONCLUSION

Feel free to ask questions and be part of my network on Linkedin, let’s collaborate on Github, and you follow me on Twitter to get more exciting insights.