Bit Manipulation – Bitwise arithmetic & logic

Introduction

In this blog, I explore several interesting result with when adding and performing bitwise logic in binary.

Concepts

Common properties for all AND, OR, XOR bitwise logics are:

Identity

Logic	Properties
AND	`A & 0 = 0, A & A = A`
OR	`A \| 0 = A, A \| A = A`
XOR	`A ^ 0 = A`

Commutativity

Logic	Properties
AND	`A & B = B & A`
OR	`A \| B = B \| A`
XOR	`A ^ B = B ^ A`

Associativity

Logic	Properties
AND	`(A & B) & C = A & (B & C)`
OR	`(A \| B) \| C = A \| (B \| C)`
XOR	`(A ^ B) ^ C = A ^ (B ^ C)`

Distributivity

Logic	Properties
AND	`A & (B \| C) = (A & B) \| (A & C)`
OR	`A \| (B & C) = (A \| B) & (A \| C)`
XOR	`A ^ (B ^ C) = (A ^ B) ^ (A ^ C)`

Absorption (with exception XOR)

Logic	Properties
AND	`A & (A \| B) = A`
OR	`A \| (A & B) = A`

XOR properties

If we take XOR of zero and some bit, it will return that bit: a⊕0=a
If we take XOR of two same bits, it will return 0 (self inverse): a⊕a=0
Inversion: if we apply XOR with the same number twice returns the original: A ^ B ^ B = A
XOR is modulo 2 addition: a⊕b=(a+b) mod 2
If 2 numbers have opposite signs then a⊕b < 0

NOT Operation (`~`)

Complement: ~A = -(A + 1)
Inversion: Flips all the bits in a number (0 to 1 and 1 to 0)

Binary Addition Rules

1 + 1 = 10 (which means 0 with a carry of 1)
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1

The sum of 2 positive numbers could be done by XOR logic continuously:

sum (x,y):
    while (y != 0) {                            // loop still carry = 0
       int answer = x ^ y;                      // sum without carry
       int carry = (x & y) << 1;                // carry
       x = answer;
       y = carry;    
    }
    return x;

Binary Substraction Rules

0 - 0 = 0
1 - 0 = 1
1 - 1 = 0
0 - 1: Borrow 1 from the next significant bit (10 - 1 = 1)

The substraction of 2 positive numbers could be done by XOR logic continuously:

substract (x,y)             // x must be greater than y
     while (y != 0) {
          int answer = x ^ y;
          int borrow = ((~x) & y) << 1;
          x = answer;
          y = borrow;    
     }
     return x;

Problem Implementing Addition

The problem Sum of Two Integers demonstrates powerful usage of XOR bitwise logic.

#include <iostream>
#include <cmath>

class Solution {
public:
    int getSum(int a, int b) {
        int x = std::abs(a), y = std::abs(b);
        // ensure that abs(a) >= abs(b)
        if (x < y) return getSum(b, a);

        // abs(a) >= abs(b) --> 
        // a determines the sign
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            // sum of two positive integers x + y
            // where x > y
            while (y != 0) {
                int answer = x ^ y;
                int carry = (x & y) << 1;
                x = answer;
                y = carry;
            }
        } else {
            // difference of two positive integers x - y
            // where x > y
            while (y != 0) {
                int answer = x ^ y;
                int borrow = ((~x) & y) << 1;
                x = answer;
                y = borrow;
            }
        }
        return x * sign;
    }
};

int main() {
    Solution sol;
    std::cout << sol.getSum(3, 5) << std::endl; // Output: 8
    std::cout << sol.getSum(-2, 3) << std::endl; // Output: 1
    return 0;
}

Problem Binary number with alternating bits

The problem requests to check if a binary representation of a number has alternating bits.

This problem is marked as easy, but bit manipulating solution is very clever! It uses bit arithmetic addition, bitwise logic AND as well as bit masking! It is based on the following observation:


             10101010101
         +    1010101010    ( input number >> 1 )
         ---------------
         =   11111111111
         &  100000000000
         ---------------
         =             0

For C++, the problem has overflow issue that needs to be handled. INT in C++ has 32 bits and a limit range up to 2,147,483,647. Therefore,

we cannot take 2,147,483,647 and add 1 like in the above logic. That number doesn't have alternating bit, thus we could just return false.
any number that is multiplied by 2 and greater than 2,147,483,647 will cause overflow. The way to fix this is to cast 32 bits integer to 64 bits integer.

Code:

class Solution {
public:
    bool hasAlternatingBits(int number) {
        // Handle edge case for maximum unsigned int value
        if (number == INT_MAX) {
            return false;
        }

        // Use 64-bit integers to avoid overflow
        uint64_t tmp = static_cast<uint64_t>(number) + (static_cast<uint64_t>(number) >> 1);
        return (tmp & (tmp + 1)) == 0;
    }
};

Problem Find a non-duplicate number in an array

The problem Single Number makes clever used of XOR logic: a number XOR with itself returns zero:

If we take XOR of zero and some bit, it will return that bit: a⊕0=a
If we take XOR of two same bits, it will return 0: a⊕a=0

To detect a duplicate, we just use a number `a` and XOR with all numbers in the array.

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b ==> the non-duplicate is b

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0;
        for (int i : nums) {
            a ^= i;
        }
        return a;
    }
};

Time complexity is O(N) for N is the array size. If hashmap (unordered_map) solution is used, time complexity is also O(N).