Bit Manipulation Problems

I’ve always sucked at bit manipulation problems so I read up on it and will go into stuff I learned and some of the problems I’ve done. Will try my best to keep this list regularly updated (no promises…)

I wont go into binary operations (AND, OR, XOR, LEFT and RIGHT BITSHIFT) since they are trivial, but I will go into what you can do with those.

• Setting the ith bit of x to 1: x |= (1 << i)
• Clearing the ith bit of x: x &= ~(1 << i)
• Toggling the ith bit of x (from 0 to 1 or 1 to 0): x ^= (1 << i)
• Checking if the ith bit is set: if x & (1 << i) != 0, the ith bit is set
• Checking if a number x is even or odd: if x & 1 == 0, x is even
• Checking if a number is a power of 2: if x > 0 and x & (x - 1) == 0, x is a power of 2

Real life example

• In error detection and correction algorithms like checksums or parity bits, bit manipulation promotes data integrity during transmission by identifying and correcting errors in the binary data.
• IP addresses and subnet masks use bitwise AND operations to determine whether two devices are on the same network.

Implementations

Some implementation stuff from doing problems:

https://leetcode.com/problems/number-of-1-bits/

Hardware POPCNT: Modern CPUs have a dedicated hardware instruction designed specifically to count set bits, often called “population count” or POPCNT. In C++, compilers give you direct access to this via built-in functions. It often runs in a single CPU cycle. It is the absolute fastest way to count bits in C++.

Note: If n is a 64-bit long integer, you would use __builtin_popcountll(n) instead

https://stackoverflow.com/questions/57150666/how-does-builtin-popcount-of-gcc-work

class Solution {
public:
    int hammingWeight(int n) {
        return __builtin_popcount(n); // counts number of 1 bits
    }
};

Brian Kernighan’s Algorithm: uses a neat bitwise trick: n &= (n - 1). If a number only has two 1s (like 10000000000000000000000000000010), the standard loop takes 32 steps. This algorithm takes exactly 2 steps. The time complexity drops from O(32) to O(k), where k is the number of set bits.

class Solution {
public:
    int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            n &= (n - 1); // Clears the lowest '1' bit
            cnt++;
        }
        return cnt;
    }
};

https://leetcode.com/problems/single-number/description/

for this problem the key insight was that XOR is associative and commutative (order doesn’t matter: A ^ B ^ A is the same as A ^ A ^ B, which is 0 ^ B, which is B).

and the implementation can be simplified using std::accumulate. Also since C++20, std::accumulate can be marked as constexpr and be evaluated at compile time. This allows you to offload calculations to the compiler, leaving zero runtime overhead for the final output.

#include <numeric>
#include <functional>

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return std::accumulate(nums.begin(), nums.end(), 0, std::bit_xor<int>());
    }
};

C++17 (Alternative introduced): While not a change to std::accumulate itself, C++17 introduced std::reduce, which functions similarly but allows for parallel execution.

https://leetcode.com/problems/single-number-iii/

This problem was also interesting since we needed to make use of 2s complement. 2s complement is a way which allows us to represent negative numbers in binary. How it works is you have a positive number, let’s say 10, convert it to binary. you will get: 00001010

according to 2s complement -10 will be represented as: ~x + 1 where its just invert bits of x + 1.

~10 becomes 11110101 and 11110101 + 1 becomes 11110110 (which is -10).

The reason this is important is because in the question we are supposed to identify 2 numbers which are unique in the array. The 2 numbers are unique (or else they would become 0 when xor’d). when we perform and operation between +6 and -6 (where 6 is the result of xor ops) for example, it will give us the bit which is different between the 2 unique numbers. For example:

  ...00000110  (6)
& ...11111010 (-6)
-----------------
  ...00000010  (2)

Our diff is 2 (binary 010). This tells us that our two unique numbers (3 and 5) have different values at the second bit from the right. From there the problem became straightforward.