Programming Puzzle: Fun with Bitwise Operations, Part 1

Hi, today I want to share solutions to some pretty small programming puzzles. There are threee of them:

1. Switch the values of 2 int variables without introduction of additional variable
2. Check if the int number is a palindrome in binary notation
3. Implement sum of two int variables with only binary operations, such as ^ & | or shifting (<<, >>)

So if you are interesting in explanation for the solutions, read further. Or check the source code otherwise.

1. Switching values of 2 variables without 3rd variable. 

The classic approach to switch value is the following

def exchange_classic(x, y):
    tmp = y
    y = x
    x = tmp
    return x, y

Here we have an additional variable tmp to store a value of y and then assign it to x

But the same result can be achieved with XOR operation: 

def exchange(x, y):
    x = x ^ y
    y ^= x
    x ^= y
    return x, y

It's a bit trickier approach, so let's consider an example, x = 5 (101b), y = 6 (110b), by executing x^y we found at which positions the bits are differ (x ^ y = 011b = 11b), next you say, switch the bits for y = 6 ^ 11b = 110b ^ 11b = 101b (getting initial value of x) and then, x = current-value-of-y ^ 11b = 101b ^ 11b = 110b.

2.  Checking if the value is a palindrome in binary notation

The idea is to check if the value has the same binary representation if it's reversed. For example, if we have say 5 = 101b the reversed is 101b as well. If we have 6 = 110b the reversed is  011b = 3

How can we check that a reverse has the same binary represetation, there are several approaches, and the most natural one is "original == reversed" (the values are simply match), or you can something like this original & reversed == original, or even original ^ reversed == 0 :)

Another question is how to revert the binary represenation. Set reversed = 0. Iteratively pick the last significant bit from an original int, append it to the beginig of reversed value.

Combining these ideas together:

def palindrome(x):
    """Checks if the integer is a palindrome in binary representation, ex: 5 = 101 - true, 8 = 1010 - false"""
    original = x
    reverse = 0
    while x > 0:
        reverse <<= 1
        reverse += x % 2 //in fact we can do even better x&1 instead of x%2
        x >>= 1

    return reverse == original

3. Sum of two variables using only bitwise operations

Let's consider an example sum(3, 1) = 11b + 1b, how do we sum in binary representation? 

If there are overlapping 1s in some position, we put 0 and adding 1 to a next position. 

Considering an example 11b + 1b:

1. 11b + 1b = 10b + (overlapping 1 in first position shifted << 1) = 10b + 10b
2. 10b + 10b = 00b + (overlapping 1 in second position shifted << 1) = 00b + 100b
3. 00b + 100b = 100b + (no overlapping 1s - stop)

So combining these ideas in programming code we get: 

def add(x, y):
    """Adds x to y using only bitwise operations """
    if x < 0 or y < 0:
        raise ValueError("Arguments must be non-negative, provided {}, {}".format(x, y))

    if y == 0:
        return x

    summ = x ^ y  # Summing all the positions, zeroing overlapping 1-s, example 3 ^ 1 = 2
    carry = (x & y) << 1  # Finding a curry, for example 3, 1 => 3 & 1 = 1, so shift curry one bit left curry = 2,
    return add(summ, carry)

Ta-daaaa-daam :)