Examples of optimizations using bit-shifting and more

And the compiler gazed upon the code, and it was slow. And the coder, weary from inefficiency, raised their hands and declared, 'Let there be optimizations!' And thus, with bit-shifts and clever tricks, the code was transformed, faster than ever before. And it was good. Welcome, dear reader, to the realm of C++ optimizations, where every cycle counts and efficiency reigns supreme.

Multiplication and Division by Powers of Two

Multiplying and dividing by powers of two can be optimized using bit-shifting. Since each left shift (<<) multiplies a number by 2, and each right shift (>>) divides a number by 2, this is a faster alternative to standard multiplication and division.

Example: Multiplication by 8 (which is 2^3)

Without optimization:

int multiplyBy8(int x) {
    return x * 8;
}        

With bit-shift optimization:

int multiplyBy8(int x) {
    return x << 3;  // Equivalent to x * 8
}        

Division by 4 (which is 2^2)

Without optimization:

int divideBy4(int x) {
    return x / 4;
}        

With bit-shift optimization:

int divideBy4(int x) {
    return x >> 2;  // Equivalent to x / 4
}        

. Swapping Two Numbers Without a Temporary Variable

Normally, swapping two integers requires a temporary variable, but this can be done more efficiently using bitwise XOR.

Example:

Without optimization:

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}        

With XOR optimization:

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

This approach works because XOR-ing the same value twice cancels it out, leaving the original value.

Checking if a Number is Even or Odd

Rather than using modulo operations (%) to check if a number is even or odd, bitwise AND can be used, which is faster.

Without optimization:

bool isEven(int x) {
    return (x % 2 == 0);
}        

With bitwise optimization:

bool isEven(int x) {
    return (x & 1) == 0;  // Even numbers have 0 as the least significant bit
}        

Clearing the Lowest Set Bit

To clear (set to 0) the lowest set bit in an integer, instead of using loops or conditionals, you can use the following bitwise trick:

int clearLowestSetBit(int x) {
    return x & (x - 1);
}
        

This works because subtracting 1 from a number flips all bits after the lowest set bit (including the lowest set bit itself), and the bitwise AND operation clears the lowest set bit.

Counting Set Bits (Brian Kernighan’s Algorithm)

Instead of looping through all bits of a number to count the set bits (1s), you can use a faster approach by clearing the lowest set bit in each iteration.

Without optimization (naive approach):

int countSetBits(int x) {
    int count = 0;
    while (x) {
        count += (x & 1);
        x >>= 1;
    }
    return count;
}        

With optimization (Brian Kernighan’s algorithm):

int countSetBits(int x) {
    int count = 0;
    while (x) {
        x = x & (x - 1);  // Clears the lowest set bit
        count++;
    }
    return count;
}        

Fast Exponentiation Using Bit Manipulation

Exponentiation can be optimized using a method called "exponentiation by squaring" which is much faster than na?ve multiplication loops.

(raising base to the power of exp):

int power(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) {      // If exp is odd, multiply result by base
            result *= base;
        }
        base *= base;       // Square the base
        exp >>= 1;          // Divide exp by 2
    }
    return result;
}        

This approach reduces the time complexity from O(exp) to O(log(exp)) by squaring the base and halving the exponent at each step.

• Shifting left (<<) is equivalent to multiplying by powers of two.
• Shifting right (>>) is equivalent to dividing by powers of two.
• Using XOR (^) can replace temporary variables in swapping.
• Using AND (&) can check for even/odd or clear bits efficiently.

These examples demonstrate how bitwise operations can make certain operations faster and more efficient, especially in performance-critical systems like embedded software or high-performance computing.