Bitwise Operations and tricks

You likely already know basic logical operations like AND and OR. Using if(condition1 && condition2) checks if both conditions are true, while OR (c1 || c2) requires at least one condition to be true.

Same can be done bit-per-bit with whole numbers, and it's called bitwise operations. You must know bitwise AND, OR and XOR, typed respectively as & | ^, each with just a single character. XOR of two bits is 1 when exactly one of those two bits is 1 (so, XOR corresponds to != operator on bits). There's also NOT but you won't use it often.

#include <bits/stdc++.h>
using namespace std;

// convert integer to binary
string to_binary(int x) {
   string s;
   while (x > 0)
   {
      s += (x % 2 ? '1' : '0');
      x /= 2;
   }
   reverse(s.begin(), s.end()); // MSB needs to be at first
   return s;
}

int main()
{
   cout << "13 = " << to_binary(13) << endl; // 1101
   cout << "13 = " << bitset<8>(13) << endl; // prints a number after converting it into a bitset.

   int x = 53;
   int y = 28;
   cout << "x = " << to_binary(x) << ", y = " << to_binary(y) << endl;

   cout << "AND, OR, XOR:" << endl;
   cout << to_binary(x & y) << " " << to_binary(x | y) << " " << to_binary(x ^ y) << endl;
}

// output: 
13 = 1101
13 = 00001101
x = 110101, y = 11100
AND, OR, XOR:
10100 111101 101001

There are also bitwise shifts << and >>, not having anything to do with operators used with cin and cout. As the arrows suggest, the left shift << shifts bits to the left, increasing the value of the number. The right shift >> shifts bits to the right, decreases the value.

Tricks:

1. Playing with the K-th bit:

Perform various operations on K-th bit.

// check if the K-th bit is set
x & (1 << k)

// set the K-th bit
x | (1 << k)

// unset the K-th bit
x & ~(1 << k)

// toogle the K-th bit
x ^ (1 << k)

2. Checking if a Number is Odd or Even (get the last bit)

bool isOdd(int n) {
    return n & 1;
}

3. Checking if a Number is a Power of Two

A number is a power of two if it has a single one bit in its binary representation. 4=100, 8=1000, 16=10000 etc. So, let n =00100000. That makes n-1 = 00011111. So,

0 0 1 0 0 0 0 0

& 0 0 0 1 1 1 1 1

0 0 0 0 0 0 0 0

So, only if (n & (n-1)) == 0 then that number is a power of two.

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Exception is zero. So, check first that the number is not zero at first.

4. Counting the Number of 1s (Hamming Weight)

To count the number of 1s in the binary representation of a number, you can repeatedly clear the lowest set bit (1 is also called set bit) using n & (n - 1). n-1 clears the lowest set bit or turns 1 to 0.

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}

Let n = 13 (binary 1101):

1. First iteration

   • n = 1101 (13)

   • n - 1 = 1100 (12)

   • n & (n - 1) = 1101 & 1100 = 1100

   • Lowest 1 (at position 0) is cleared

   • count = 1

2. Second iteration

   • n = 1100 (12)

   • n - 1 = 1011 (11)

   • n & (n - 1) = 1100 & 1011 = 1000

   • Lowest 1 (at position 2) is cleared

   • count = 2

3. Third iteration

   • n = 1000 (8)

   • n - 1 = 0111 (7)

   • n & (n - 1) = 1000 & 0111 = 0000

   • Last 1 cleared

   • count = 3

4. Loop ends (n = 0)

Final result: 3 set bits

5. Getting the Lowest Set Bit

n & -n leaves only the lowest 1 bit. -n is the two’s complement of n, which flips all the bits of n and adds 1. e.g: (10)2 = 00001010, (-10)2 = 11110110. So, n & -n = 00000010.

int getLowestSetBit(int n) {
    return n & -n;
}

6. Reversing the Bits of a Number

Reversing the bits of a number is a common problem in low-level programming. You can reverse the bits of a number using bitwise operations. The loop iterates through all 32 bits of the number. The least significant bit of n is extracted using n & 1 and added to the result. The result is shifted left to make space for the next bit, and n is shifted right to process the next bit.

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;          // Shift result left to make space for the next bit
        result |= (n & 1);     // Add the least significant bit of n to result
        n >>= 1;               // Shift n right to process the next bit
    }
    return result;
}

• int is a signed integer type by default, meaning it can represent both positive and negative values, including zero. uint32_t is an unsigned integer type, meaning it can only represent non-negative values (zero and positive integers).

• int has an implementation-defined size, which means its size can vary depending on the system and compiler being used. While it's commonly 32-bit on many modern systems, it could be 16-bit or 64-bit on others. uint32_t is a fixed-width integer type defined in <stdint.h>. It is guaranteed to be exactly 32 bits wide, regardless of the system or compiler. This makes it suitable for situations requiring precise control over data representation, such as hardware interaction or network protocols.

• Due to its signed nature and variable size, the range of int can vary. For a 32-bit int, the range is typically from -2,147,483,648 to +2,147,483,647. Because uint32_t is unsigned and fixed at 32 bits, its range is consistently from 0 to 4,294,967,295. This allows it to store a larger maximum positive value than a 32-bit int because it does not need to reserve a bit for the sign.

7. Checking if Two Numbers Have Opposite Signs

By using XOR. If the sign bits of x and y are different, the sign bit of x ^ y will be 1.

bool haveOppositeSigns(int x, int y) {
    return (x ^ y) < 0;
}

8. Check Equality:

(a ^ b) == 0; // a == b
!(a ^ b)      // same

9. Multiply or divide a number by 2 to the power k:

// multiplicaiton
x << k

// division
x >> k

Multiplication: Left shift by k. e.g: 1010 (10) « 2 = 101000 (40)

Division: Left shift by k. e.g: 1010 (10) » 2 = 0010 (2)

10. Turning Uppercase Letters to Lowercase (or Vice Versa)

Uppercase letters (‘A’-’Z’) have ASCII values from 65 to 90. Lowercase letters (‘a’-’z’) have ASCII values from 97 to 122.

The difference between uppercase and lowercase is a single bit: the 6th bit (counting from 0). To convert an uppercase letter to lowercase, you can set the 6th bit using the bitwise OR (|) operator:

char toLower(char c) {
    return c | (1 << 5);
}

(1 << 5) creates a binary number where only the 6th bit is set (e.g., 00100000 in binary). The | operator ensures that the 6th bit is always set, effectively converting uppercase to lowercase.

Similarly, to convert a lowercase letter to uppercase, you can clear the 6th bit using the bitwise AND (&) operator with the complement of (1 << 5):

char toUpper(char c) {
    return c & ~(1 << 5);
}

~(1 << 5) creates a mask where all bits are 1 except the 6th bit, which is 0. The & operator clears the 6th bit, converting lowercase to uppercase.

11. Round down or floor a number:

n >> 0; // 5.1234 >> 0 = 5

12. Swapping Two Numbers Without a Temporary Variable

This works because XOR has the property that a ^ a = 0 and a ^ 0 = a.

void swap(int &a, int &b) {
    a = a ^ b;
    b = a ^ b; // becomes (b = (a ^ b) ^ b = a)
    a = a ^ b; // becomes (a = (a ^ b) ^ a = b)
}

• Initially a is a = a ^ b

• In second line b = a ^ b , we get b = (a ^ b) ^ b where b ^ b = 0 and we get b = a

• Likewise, in a = a ^ b , we get a = b

13. Finding the Only Non-Repeating Element in an Array

If every element in an array appears twice except for one, you can find the unique element using XOR. This works because a ^ a = 0 and a ^ 0 = a So all duplicate elements cancel out and only the unique one remains.

int findUnique(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

References:

1. https://codeforces.com/blog/entry/73490

2. https://www.youtube.com/watch?v=LGrE0siZ-ZA

3. https://medium.com/@r.siddhesh96/10-bitwise-tricks-you-should-know-with-examples-in-c-4b04820dfbc0