Starters of Bit manipulation basics:

Let’s talk the language of computers i.e. 0s and 1s, and try to leverage the logic of Binary fields and manipulate them for our motives ( the way your ex maipulated you XD)

Basic operators that wer already know:

& BITWISE AND - always shrink / keep the value

BITWISE OR - increases or same the value

~ BITWISE NOT - flip the bits

^ BITWISE XOR - flipping the specific bits

LEFTSHIFT Multiplication ( a<<b = a* 2^b)

<< RIGHTSHIFT - Division/trunacting By 2 ( a>>b = a^2-b)

1. Converting Decimal numbers to Binary ( written r to l ):

Well, if you an engineer, you ought to know the algorithm behind conversion between different base values, if you have electronics major, that’s just peanuts for you.

Let’s use vector ( STL C++) to contain the binary

// Converting the decimal into binary equivalent ( not the 32 bits, but the required ones)
vector<int> convertIntoBinary(long long n ){
	vector<int> binary;
	while(n){
		bitest.push_back(n&1);
		n >>= 1;
		}
		reverse(binary.begin(), binary.end());
	return binary;
}
// Time COmplexity: O(log2N) -- We are dividing each time by 2
// SpaceCOmplexity: O(log2N) -- No of different indexes which can depend on n		
long long convertIntoDecimal( vector<int>& binary){
	long long n = 0;
	for(int i =0; i< binary.size(); i++){
			n = ((n<<1)|(binary[i]&1));
		}
		return n;
}
// Time Complexity : O(N) - to iterate through all th elments
// Space Complexity: O(1) - for n- long long 64 bits for max 10^18 number

Examples: 5 → (101) ,10 →(1010)

The maximum value of n in programmin gwe can encounter is : n = 10e18

the binary indices for such n at max is log2(10e18) = 64 → long long

Pattern:

  1. Important optimisation : converting binary string ( such as visited array in graph ) into single number makinbg it O(1)
  2. 32-bit Integer range - roughly 210e9 to -210e9 i.e. 32 bits (log2(2*10e9)) == 32
  3. Representing negative number - sign bit → 1’s complement and add +1 in rightmost side (2’s complement) and add

XOR Properties:

a^a = 0

a^ 0 = 0

Flipping the specific bits

say B1 = (00101) , if we need to flip the 3rd bits from the right

use mask = 00100 (1<<i)

mask^B1 = (00001)

Bit Masks:

masks affects what we need to affect

higlighting the specfifc bit at the ith position

How to make them 0001000 types-mask1 : (1<<i)

Setting a bit at position ith: n | (1<<i)

Unsetting a bit at ith position: n & (~(1<<i))

Checking if ith bit is set

bool check = (n&(1<<i));

if check is 1, ith bit is set, else it’s unset

Removing rightmost set bit

Used in Fenwick algorithms, power of 2 bit problems, removing the last set bit

  1. Approach 1 : Used in Fenwick trees

    id -= (id&-id)

    For e.g. → id = 1101100

  2. Approach 2 : Using Another techinque:

    id = (id&(id-1))

    eg1: n = 12 → (1100)

    ⇒ n-1 = 11 → (1011)

    11 & 12 = 1 0 0 0

    eg2 : n = 13 → 1101

    ⇒ n-1 = 12 → 1100

    ⇒ n-1 & n → 1100

    eg3: n = 8 → 1000

    ⇒ n-1 = 7 → 0111

    ⇒ n-1 & n → 0000 = 0

    // Observation if (n& (n-1)) == 0 , n is the power of 2

    // Reason: As power of 2 will contain only one set bit, thus removing the rightmost set bit, will leave nothing but zeros.

Making mask of the number with its rightmost bit

Say number n = 10 (1010), rightmost bit at 2nd position, required mask = 0010

We can use the property as mask = n& ~(n-1)

Dry run: n = 1010

n -1 = 9 = 1001

~(n-1) = 6 = 0110

& n = 10 = 1010

mask = 0010

counting set bits from 1 to n:


    // n: input to count the number of set bits
    //Function to return sum of count of set bits in the integers from 1 to n.
    int countSetBits(int n)
    {   n++;
        int count = 0;
        for(int i = 2; i/2<n; i*=2){
            count += ((n/i)*i)/2;
            if(n%i > i/2) count += n%i - i/2;
        }
        return count;
    }

Refer to Aryan Mittal’s recommeded videos:

Easy

  1. Making use of bitArray & adding nums in bitArray -