Road to C++ Programmer #24 - Bit Manipulation

C++DSA

Last Edited: 2/1/2025

The blog post introduces bit manipulation in C++.

CPP Bit

After all, all data is expressed in binary. For example, an unsigned integer can be expressed in 4 bytes or 16 bits. Hence, working directly with bits is typically faster. In this article, we will discuss bitwise operators that let us work with bits directly and how these operators can sometimes make the code faster.

Bitwise Shift Operators

There are operators called bitwise shift operators that can shift bits left and right. For example, the left shift operator can shift 0101 to 1010, and the right shift operator can shift 0101 to 0010. For an unsigned integer, each bit represents a multiple of 2 starting from 1, moving from right to left. This means bitwise shift operators can perform multiplication and integer division by 2n2^n by shifting nn times, as shown below.

int a = 5; // 0101
int b = a << 2; // 10100 = b = 5 * 2^2 = 20
int c = a >> 1; // => 0010 = c = 5 // 2*1 = 2

The above shows the left shift operator, <<, and the right shift operator, >>, applied to the integer 5 twice and once, respectively. As discussed, shifting nn times to the left and right corresponds to multiplying and dividing by 2n2^n. It tends to be faster to use bitwise shift operators to perform multiplication and division by a multiple of 2, though the compiler can often apply such optimizations automatically when compiling the code to Assembly. Hence, it is almost always better to use b = a * 2 instead of b = a << 2.

Bitwise Logical Operators

There are four bitwise logical operators: AND (&), OR (|), XOR (^), and NOT (~), which apply their logic to every bit of two numbers. The following is an example demonstrating how the bitwise logical operators work.

int a = 5; // 0101
int b = 6; // 0110
 
// AND
int c = a & b; // => 0100 = 4
 
// OR
int d = a | b; // => 0111 = 7
 
// XOR
int e = a ^ b; // => 0011 = 3
 
// NOT
int f = ~a; // => 1010 = 10

The AND operator outputs 1s only when the bits in the same position are both 1s, the OR operator outputs 1s except when both bits are 0s, the XOR operator outputs 1s when the bits are different, and the NOT operator flips bits.

Example Usage

They are rarely useful in many cases, but using them appropriately can lead to massive performance improvements. One scenario where bit manipulation comes in handy is when we need to find a sequence of 10 unique characters from a sequence of characters. Before diving into bit manipulation, the most intuitive approach to this problem is to use a hash set (or unordered set), where we iterate over the sequence, store 10 characters in the set, and count the number of elements in the set.

int hash_approach(vector<char> input) {
    int index = 0;
    
    while (index != input.size() - 10) {
        unordered_set<char> set;
        for (int i = index; i < index + 10; i++) {
            set.insert(input[i]);
        }
        if (set.size() == 10) {
            return index + 10;
        }
        index++;
    }
    return EXIT_FAILURE;
};
 
int main () {
    char chars[18] = {'a','s','o','i','q','l','m','o','v','c','p','z','x','y','h','j','n','m'};
    vector<char> input(chars, chars + sizeof(chars) / sizeof(chars[0]));
 
    auto start = std::chrono::high_resolution_clock::now();
    int result = hash_approach(input);
    auto end = std::chrono::high_resolution_clock::now();
    cout << "Result: " << result << endl; // => Result: 13
    std::chrono::duration<double> duration = end - start;
    cout << "Time: " << duration.count() << " seconds" << endl; 
    // => Time: 3.3875e-05 seconds (in my config)
 
    return 0;
};

Since a hash set stores only unique elements, we can guarantee termination when we observe a sequence of 10 unique characters. Using the chrono standard library, the execution time of this algorithm was measured at 3.39×10−53.39 \times 10^{-5} seconds. Given that hash set lookup is O(1)O(1), the algorithm’s time complexity is O(n)O(n). Alternatively, we can use a vector to store unique elements.

int vector_approach(vector<char> input) {
    int index = 0;
    
    while (index != input.size() - 10) {
        vector<char> vec;
        for (int i = index; i < index + 10; i++) {
            if (find(vec.begin(), vec.end(), input[i]) == vec.end()) {
                vec.push_back(input[i]);
            }
        }
        if (vec.size() == 10) {
            return index + 10;
        }
        index++;
    }
    return EXIT_FAILURE;
};

In theory, vector lookup takes O(n)O(n) instead of O(1)O(1), making the vector slower. However, time complexity describes how runtime scales with increasing input size. Since the window size here is fixed, lookup can be performed in constant time, making the vector implementation likely faster than the hash set implementation (no hash computation), measuring 2.58×10−52.58 \times 10^{-5} seconds. This reminds us that time complexity should always be taken with a grain of salt.

Finally, we can explore how bit manipulation can be used to solve this problem efficiently. The characters from a to z are mapped to 97–122 in the ASCII table, which can be transformed into integers from 0 to 31 by applying the modulo operation with 32. By shifting 1 left by these values, we can represent each character as a binary number with a unique position set to 1 while the others remain 0.

Bit Approach

By taking the XOR of 10 such binary values (extracting only unique values) and counting the number of 1s, we can determine the number of unique characters. If the result contains exactly 10 ones, we return the last index. Otherwise, we can remove the first character of the previous window by applying XOR again and add the next character’s binary representation with XOR. We continue this process until we obtain 10 ones. The above diagram visualizes how the process works.

int bit_approach(std::vector<char> input) {
    int filter = 0;
 
    for (int i = 0; i < 9; ++i) {
        filter ^= 1 << (input[i] % 32);
    }
 
    for (int i = 10; i < input.size(); ++i) {
        filter ^= 1 << (input[i] % 32);
        if (std::bitset<32>(filter).count() == 10) {
            return i + 1;
        }
        filter ^= 1 << (input[i - 9] % 32);
    }
 
    return EXIT_FAILURE;
};

Instead of storing characters in a window using a vector or a hash set, we can use a single integer and treat it as a binary representation. The number of 1s can be counted by casting the integer to bitset<32> and using the count method. This approach measured 1.042×10−61.042 \times 10^{-6} seconds, which is roughly 30 times faster than the previous two approaches. (Usually, time measurements and algorithm comparisons involve running them multiple times over various inputs.) This example demonstrates the power of bit manipulation in boosting performance, though whether bit manipulation should be used depends on the problem context.

Conclusion

In this article, we covered bitwise shift operators, bitwise logical operators, and a use case for bitwise operations. To reiterate, it is important to consider whether bit manipulation is appropriate, based on the trade-offs.

Resources

Back to Top↑