Your guide to Bit Manipulation
--
I though it may look easy, but it can become super tricky. My biggest problem with bit manipulation is that a very tiny mistake could lead into a catastrophic error in the expected solution.
Bit manipulation is the process of applying logical operations on a sequence of bits to achieve a required result.
First of all, we need to be aware of the basic operators that we have…
(a) & (and)
(b) | (or)
(c) ^ (xor)
(d) ~ (not)
(e) >> (right shift)
(f) << (left shift)
&
It’s only true if both are true.
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
|
It’s true if any of the inputs is true
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
^
It’s true in case of odd numbers
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
~
Flips the input
~ 0 = 1
~ 1 = 0
Right shift
divides by two
Left shift
multiplies by two
Bit Facts
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0x & 0s = 0
x & 1s = x
x & x = xx | 0s = x
x | 1s = 1
x | x = xx ^ 0 = x
x ^ 1 = x
x ^ x = 0
Two’s Complement
Integers are usually stored in computers in the form of two’s complement. A positive number is represented normally with a 0 in the sign bit while a negative number is represented as the two’s complement of its absolute value but with a 1 in the sign bit
Example
7 = 0 111-7 = 1 001
Logical Shift vs Arithmetic Shift
Logical shift right simply inserts a 0 in the sign bit even if it was a negative number and shifts the entire bits to the right. While the Arithmetic shift keeps the sign bit and shifts the bits starting from the one that follows the sign bit
Logical shift right is represented by >>> while arithmetic shift right is represented by >>
Common Bit Tasks
Set Bit
Get Bit
Clear Bit
Update Bit
BIT TRICKS
- Check if a given number is even?
if the least bit is 0, this can be done by using the bit-wise AND
(x & 1 ) == 0 0110 (6)
& 0001
= 0000 TRUE
- Check if the number is a power of 2?
a number that is a power of two, should only have one 1 set;
if we subtract 1, all the zeros following will be set to one. If we & that with the original number we get 0
(x & x-1) == 0
✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.
