BITMASK
Basmala Ibrahim Session No.7
Content
Revision
Introduction
Algorithms and Notes
Common Tricks
Problems
Links
Revision
• Number System : a way to represent numbers using a specific base
• Base (10) :
235 => represented as (5 * 10 ^ 0 + 3 * 10 ^ 1 + 2 * 10 ^ 2)
• Base (2) : Works only with 0's and 1's
10010 => (0 * 2 ^ 0 + 1 * 2 ^ 1 + 0 * 2 ^ 2 + 0 * 2 ^ 3 + 1 * 2 ^ 4) = 18
Revision
Code To Convert From Decimal To Binary :
stack <int> st;
int num ;
cin >> num;
while(num > 0){
[Link](num % 2) ;
num /= 2;
} => O(log num)
Revision
Code To Convert From Binary To decimal :
string s;
long long sum = 0;
cin >> s ;
for(int i = 0 ; i < [Link]() ; ++i){
If(s[i] == '1' ){
sum += (1 << ([Link]() - 1 - i));
}
}
Revision
Unsigned Numbers : use all bits in binary represtation (represent only positive)
Range = 0 to (2^(n)−1)
Signed Numbers : last bit represent sign bit if last bit is 1 then the number is
negative otherwise positive
One's Complement : Range = −(2^(n−1) −1) to (2^(n−1)−1)
Two's Complement : Range = −2^(n−1) to (2^(n−1)−1)
One's Complement : to flip all bits of a number
011 => 100
Two's Complement : to flip all bits of a number after first set bit
10100 => 01100
Introduction
• Bitwise Operators: Bitwise operators operate on individual bits of numbers
(which are represented in binary format).
1) AND (&) : used to check if a particular bit is set
=> 5 & 3 → 0101 & 0011 = 0001 → 1
2) OR (|) : Commonly used to set specific bits to 1
=> 5 | 3 → 0101 | 0011 = 0111 → 7
3) XOR (^) : used for toggling(flipping) bits
=> 5 ^ 3 → 0101 ^ 0011 = 0110 → 6
Introduction
• Bitwise Operators: Bitwise operators operate on individual bits of numbers
(which are represented in binary format).
4) NOT (~) : used to flip all bits of a number
=> ~5 → ~0101 = 1010 → -6
5) Left Shift (<<): used for multiplication by powers of 2
=> 5 << 1 → 0101 << 1 = 1010 → 10
6) Right Shift (>>) : used for division by powers of 2.
=> 5 >> 1 → 0101 >> 1 = 0010 → 2
Introduction
Introduction
• Bitmask : used to manipulate specific bits in another value using bitwise
operations
• When To Use :
1) Efficient calculations (Speed)
2) Memory optimization
3) Hashing
Notes
• a & b <= min(a , b)
•a|a=a
•a&a=a
• a | b >= max(a , b)
• a Xor b Cannot detect may be greater than a and b or
less
• a XOR a = 0 a XOR b = c , a XOR c = b , b XOR c = a
Algorithms
1) Generate All Subsets : ( n <= 20 )
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) cout << arr[i]
<< " ";
}
cout << endl;
} => O( 2 ^ n * n )
Algorithms
2) void flipAllBits(int &num) { num = ~num; }
3) void flipBit(int &num, int pos) { num ^= (1 << pos); }
4) void clearBit(int &num, int pos) { num &= ~(1 <<
pos); }
Algorithms
5) bool isBitSet(int num, int pos) { return (num & (1 <<
pos)) != 0; }
6) void setBit(int &num, int pos) { num |= (1 << pos); }
7) void toggle_Bit(int &num, int pos) { num ^= (1 <<
pos); }
Functions
1) __builtin_popcount() // To Count No of 1's at binary
representation && __builtin_popcountll() //For long
long
=> O(log n)
2) bitset<n> bt(val) //n should be determined at Compile
time
Functions
Common
Tricks
• X & 1 == X % 2 // to dectect if X is even or
odd
• X & ~((1 << i+1 ) – 1) // Clears all bits of X from
LSB to ith bit
• X & ((1 << i) – 1) // Clears all bits of X from MSB to
ith bit
Common
Tricks
• X & 1 == X % 2 // to dectect if X is even or
odd
• X & ~((1 << i+1 ) – 1) // Clears all bits of X from
LSB to ith bit
• X & ((1 << i) – 1) // Clears all bits of X from MSB to
ith bit
Problems
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
Problems
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
Links
• [Link]
• [Link]
•
[Link]
ming/
•
[Link]
•
[Link]
n/
• [Link]
Links
• [Link]
• [Link]
• [Link]
Thank You