Bit Manipulation Notes

1 — Shifting

Left shift:- move everything to the left

example:- Binary representation 01010 → 10100

Decimal representation 10 → 20

How to apply in code?

int x = 10;
x<<1;

Right shift:- move everything to the right

example:- Binary representation 01010 → 00101

Decimal representation 10 → 5

How to apply in code?

int x = 10;
x>>1;

Notice:-

Left shifting is multiplying the N number decimal by 2

Right shifting is Divide the N number by 2

2 — Shifting With Sign ( Arithmetic Shifting )

As we may know that signed integers are having left bit as 1 as a minus sign

We can convert the number to negative by Tow’s complement.

So What is Two’s Complement (very simple steps )

1- inverse

2- add one

Ex:-

18 == 00010010

Applying 1- → 11101101

Applying 2- → 00000001

Result → 11101110

So Decimal from signed 2’s complement:-

-18 → 11101110

Back to our topic ( Shifting ):-

Negative has 1 on the left

1- shift all bits normally

2- replace the last bit with one

Example:-

-23 == 11101001

1-Shifting to right → 01110100

2- add sign → 11110100

3 — Bitwise Operators

Bitwise operators are good for saving space and sometimes to cleverly remove dependencies.

check if a given number is a power of 2

Consider a number N and you need to find if N is a power of 2.

• Now think about the binary representation of (x-1).
• (x-1) can be obtained by simply flipping all the bits to the right of 1

Ex : 16 = 10000–15 = 1111

10000 & 01111 → 00000

So the Rule is the number is power of 2 if ( x & (x-1) ) = 0

To make sure let’s take a look of power 2 binaries

2, 4, 8, 16 ,32

10 , 100, 1000 ,10000 ,100000

Replace 1 with zero and flip zeros we easily get ( X -1 )

!(x & (x-1) ==!0 == true

Simple Condition we can check if is the power of 2 or not without needing to loop and make O(logN).time now its constant time:-

bool isPowerOfTwoUsingBitWise(int x) {
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

let’s find more bit manipulation problems here

https://leetcode.com/tag/bit-manipulation/