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

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.

- Switch the values of 2 int variables without introduction of additional variable
- Check if the int number is a palindrome in binary notation
- 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

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:

**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:

- 11b + 1b = 10b + (overlapping 1 in first position shifted << 1) = 10b + 10b
- 10b + 10b = 00b + (overlapping 1 in second position shifted << 1) = 00b + 100b
- 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 :)

## No comments:

## Post a Comment