Bit Manipulation 🚀 ||Basics for Beginners || Concepts with all curated problems
Amit Maity
2938
Bit ManipulationCLeetCodeCareer

Bit Manipulation

xor property

  a^b=c => b^c=a
  x^0 = x
  x^x = 0

Some Important Property:

1<<n = 2^n
get ith Set bit Number: (1<<i)
get ith Unset bit Number: ~(1<<i)

## Check ith bit of a Number is Set or Not
if((a&(1<<i))!=0) cout<<"Yes";

## count set bit
__builtin_popcount(a);

a&1 == 1 (Odd digit)
a>>1 -> Divided by 2
a<<1 -> Multiply by 2
## Set ith bit of a number => 
num = num|(1<<i);

## Unset ith bit of a number => 
num = num&(~(1<<i));

## Check 2^n or Not
(n&(n-1)==0) // Yes

/*
Set union A | B
Set intersection A & B
Set subtraction A & ~B
Set negation ALL_BITS ^ A or ~A
Set bit A |= 1 << bit
Clear bit A &= ~(1 << bit)
Test bit (A & 1 << bit) != 0
Extract last bit A&-A or A&~(A-1) or x^(x&(x-1))
Remove last bit A&(A-1)
Get all 1-bits ~0
*/

### XOR of elements in the Range in [L,R] in O(1) time. 
int f(int n){
    if(n%4==0) return n;
    else if(n%4==1) return 1;
    else if(n%4==2) return n+1;
    else return 0;
}
int findXOR(int L, int R){
    return f(L-1)^f(R);
}

Amazing Resources - Bit Manipulation

Questions:
https://leetcode.com/problems/sum-of-two-integers/
https://leetcode.com/problems/single-number/

   int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto it:nums) ans^=it;  // xor of x^x=0 and x^0=x
        return ans;
    }

https://leetcode.com/problems/single-number-ii/
https://leetcode.com/problems/majority-element/
https://leetcode.com/problems/reverse-bits/
https://leetcode.com/problems/bitwise-and-of-numbers-range/

   int rangeBitwiseAnd(int left, int right) {
        if(right>left) return (rangeBitwiseAnd(left/2,right/2)<<1);
        else return left;
    }

https://leetcode.com/problems/single-number-iii/
https://leetcode.com/problems/missing-number/
https://leetcode.com/problems/counting-bits/
https://leetcode.com/problems/find-the-difference/
https://leetcode.com/problems/convert-a-number-to-hexadecimal/
https://leetcode.com/problems/hamming-distance/

   int hammingDistance(int x, int y) {
        int idx = 0;
        int ans = 0;
        while(x!=0 || y!=0){
            if((x&(1<<idx))!=(y&(1<<idx))) ans++;
            x>>=1;
            y>>=1;
        }
        return ans;
    }

https://leetcode.com/problems/set-mismatch/
https://leetcode.com/problems/binary-number-with-alternating-bits/
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
https://leetcode.com/problems/complement-of-base-10-integer/
https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/
https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
https://leetcode.com/problems/xor-operation-in-an-array/
https://leetcode.com/problems/decode-xored-permutation/
https://leetcode.com/problems/decode-xored-array/
https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/
https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

Modular Property

(a+b)%mod = ((a%mod) + ( b%mod))%mod;
(a*b)%mod = ((a%mod) * ( b%mod))%mod;
(a-b)%mod = ((a%mod) - (b%mod)+mod)%mod;
(a/b)%mod = ((a%mod) * (b^-1)%mod)%mod;

Comments (3)