## Tuesday, April 16, 2013

### 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,