Bitmasking - 1

Covered in this section:

• Introduction to Bitmasking
• Basic bitwise operations
• basic C++ stl realted to Bitwise operations

Introduction

All data in computer programs is internally stored as bits, i.e., as numbers 0 and 1. Bitmasking/Bitmanipulation involves directly working with individual bits (0s and 1s) using operations like AND, OR, XOR, and NOT :

AND operation

The and operation x & y produces a number that has one bits in positions where both x and y have one bits. For example, 22 & 26 = 18, because

OR operation

The or operation x | y produces a number that has one bits in positions where at least one of x and y have one bits.

XOR operation

The xor operation x ^ y produces a number that has one bits in positions where exactly one of x and y have one bits.

NOT operation

The not operation ~x produces a number where all the bits of x have been inverted. NOT in bitmasking is a tricky operator as its representation depends on size of data structure

            x = 29 => 00000000000000000000000000011101
            ~x = −30 => 11111111111111111111111111100010
        

Basic Bit Operations

• x << k: Shifts the bits of x to the left by k positions (equivalent to multiplying by 2^k)
• x >> k: Shifts the bits of x to the right by k positions (equivalent to dividing by 2^k, discarding remainder)
• x |= (1<<j): set the j-th item of the set.
• x &= ~(1<<j): clear the j-th item of the set.
• (1<<n)-1: set n starting bits of the number.

C++ STL

• __builtin_clz(x): he number of zeros at the beginning of the number (From MSB).
• __builtin_ctz(x): the number of zeros at the end of the number (From LSB).
• _builtin_popcount(x): the number of ones in the number

Practice Assignment

• Try solving this problem. You can also use C++ STL for convenience.
• Try solving this problem.