# Bit manipulation fun

Wednesday, January 30, 2013

So while I was working on interview prep, I got a bit curious about what cool ways bit manipulation might alter the way we might write code. Here's a few examples of short functions you can write using only bit operations.

## Simple stuff first

The following trick may be standard fare but seeing as I am not a "classically" trained programmer (no degree in computer science), this guy did tickle my fancy.

When you write out a integer in a binary representation, 5 as `0101` for example, the least significant bit (leftmost bit) represents if the integer is odd or even. Of course, bits further left represent powers of two, hence the term "base two".

```0101 is 0*(2^3) + 1*(2^2) + 0*(2^1) + 1*(2^0)
or 0*8 + 1*4 + 0*2 + 1*1
or 5
```

Anyone can write a simple function that tests if a given integer `x` is even. Usually it will involve checking to see if `x` mod 2 is 0.

```def is_even(x):
return (x % 2) == 0
```

But, given that least significant bit of a binary value represents odd or even, we can write that same `is_even` function using the `AND` bit operation.

```def is_even(x):
return (x & 1) == 0
```

For example 6 & 1 is 0.

```  0110  <-- 6
& 0001  <-- 1
======
0000
```

This ends up being the same amount of typing but it's interesting that we have this second option of writing the `is_even` function.

## Powerful twos

If you work on Project Euler problems frequently, the following shortcut might be beneficial to keep in mind. Here's a function that checks if `x` is a power of two.

```def is_power_of_two(x):
power_of_two = 2
while power_of_two < x:
power_of_two *= 2
return power_of_two == x
```

That's pretty compact but it turns out binary is well suited to figure out if a number is a power of two.

```def is_power_of_two(x):
return (x & (x-1)) == 0
```

Let's see this in action with `x` as some random binary number:

```  010110000  <-- x
- 000000001
===========
010101111  <-- x-1
& 010110000
===========
010100000  <-- x & (x-1)

So, (x & (x-1)) just removed the left-most bit that was equal to 1. But then, when might (x & (x-1)) be 0? That would only happen when x has only one 1 bit, which means that x must be a power of 2.
```

## Swapping in place

Python is nice in that you never have to use a temporary variable when you want to do variable swaps. This is, of course, not the same in other languages.

```x, y = y, x
```

Behind the scenes, Python accesses the values of `y` and `x`, then rotates them as it unpacks and assigns to `x` and `y`. Here's what that looks like when run through the Python disassembler:

```import dis

def func():
a = 1
b = 2
a, b = a, b
a, b = b, a

dis.dis(func)
>
>  3           0 LOAD_CONST               1 (1)
>              3 STORE_FAST               0 (a)
>
>  4           6 LOAD_CONST               2 (2)
>              9 STORE_FAST               1 (b)
>
>  5          12 LOAD_FAST                0 (a)
>             18 ROT_TWO
>             19 STORE_FAST               0 (a)
>             22 STORE_FAST               1 (b)
>
>  6          25 LOAD_FAST                1 (b)
>             31 ROT_TWO
>             32 STORE_FAST               0 (a)
>             35 STORE_FAST               1 (b)
>             41 RETURN_VALUE
```

But, did you know we can actually swap without a temporary variable using `XOR` too.

```x ^= y
y ^= x
x ^= y
```

To understand what's happening, you should recall that `XOR` is commutative, `x^x` is 0, and `x^0` is `x`. Let's break down the XOR Swap Algorithm again.

```start   ->  breaking down  ->  commuting      ->  cancelling ->  removing 0's
=============================================================================
x ^= y  ->  x = x^y
y ^= x  ->  y = y^x^y      ->  y = x^y^y      ->  y = x^0    ->  y = x
x ^= y  ->  x = x^y^y^x^y  ->  x = x^x^y^y^y  ->  x = 0^y^0  ->  x = y
```

That's pretty cool but I'll stick to Python's easy swap. It is nice, however, to see how binary manipulation can be used to our advantage in languages that don't have an in-place swap.

Now for the disclaimer. While the XOR swap is pretty nifty, it doesn't have much practical use. If you actually plan on using it in the real world, hopefully your application fits in one of these buckets. Turns out, optimizing compilers tend to make temporary variable swaps pretty efficient, often faster than this XOR swap.

Have any more bit manipulation tricks you'd like to share? Leave me a comment, I'd love to see more in action.