Bit Level Manipulation (Posted on April 6th, 2013)

Bit level manipulation allows us to write more efficient code due to the fact that CPU's are really good at handling bits. In fact that's all they really do. Even if you've never played around with bit manipulation it's likely that your compiler has modified your code to use bit manipulation.

Finding Odd AND Even Numbers

At some point everyone's probably written some code to this effect:

def odd_or_even(number):
    if number % 2 == 0:
        return "Even"
    return "Odd"

However, as we all know long division can be kind of annoying, so we don't want our program to have to do any of that. We all know that to check if a number is odd or even we just need to check the last digit. Well it turns out that the same is true for binary. In binary there is only one slot that contains an odd number, the first one. Therefore, any number with a 1 set in the first slot has to be an odd number. Most compilers realize this and change our code to something like:

def odd_or_even(number):
    if number & 1 == 0:
        return "Even"
    return "Odd"

The "&" operator performs a bitwise AND. If our number was 7 then it would yield 1 because only the first binary column for both numbers contains a 1. Likewise if the number was 6 then we'd get back 0.

111 (7)
001 (AND with 1)
001

110 (6)
001 (AND with 1)
000

Slide to the Left. Now Slide to the Right

Another optimization most compilers make involves division and multiplication. You probably write something like:

def double(number):
    return number * 2

def half(number):
    return number / 2

However, what you're really doing is shifting one bit to the left or one bit to the right respectively.

def double(number):
    return number << < 1

def half(number):
    return number >> 1

If our number was 6 then it would yield 12 and 3.

0110 (6)
1100 (6 after being left shifted = 12)

110 (6)
011 (6 after being right shifted = 3)

Swapping Values Without a Temporary Variable

One cool trick that can be done with bit level manipulation is swapping the values of two variables with XOR. XOR compares each column and checks if they are different or the same. If they are different than the new value for that column is one, otherwise it is 0. We can take advantage of this and swap two values in place

Wikipedia has a great graphic showing how this is done with 10 and 3.

Swapping 10 and 3 with XOR

The code for this is as such:

x = 10
y = 3
x ^= y
y ^= x
x ^= y

On a side note, if you're using Python or Ruby you could also do something like this:

x, y = y, x

I hope you found these optimizations/tricks mildly interesting. If so, in my research for other bit level tricks I found this really cool resource which is a large compilation of tricks. A lot of interesting stuff on there.

As always if you have any feedback or questions feel free to drop them in the comments below or contact me privately on my contact page. Thanks for reading!

Tags: Optimizations

Comments:

  • V - 1 year, 4 months ago

    Nice..added your link to our resources page!

    reply

  • Herve - 1 year, 4 months ago

    Cool tricks!

    reply

  • Caverna - 1 year, 4 months ago

    It's great to PIC programming...

    reply

  • D - 1 year, 4 months ago

    Really cool. I've always wondered about bit manipulation but never got around to it. Thanks.

    reply

  • Agentlien - 1 year, 4 months ago

    These tricks are useful to know, but you should clarify that most of these only work for (unsigned) integers. Also, be advised that most of these are done by most compilers implicitly, and explicitly using some of these will only serve to make it more difficult for the compiler to see your intention, and possibly lose optimization opportunities or even lead to pessimization. In particular, this quote is taken from the Wikipedia article on XOR swap: "In most practical scenarios, the trivial swap algorithm using a temporary register is more efficient."

    reply

  • pgrmdave - 1 year, 4 months ago

    Premature optimization and all that. Human readable code is written for humans and compiled for computers - the compiler is likely to take care of these, and if not it's unlikely that dividing by two is the bottleneck in your program.

    reply

  • stefan - 1 year, 4 months ago

    I have to agree with the previous poster: many of these tricks will be performed automatically by the compiler, without you having to sacrifice readability and maintainability. Moreover, you may actually decrease performance when applying such tricks, because it's possible you prevent the compiler from applying another optimization within the same context! Leave low level optimizations to the compiler unless: 1. you actually have a performance issue 2. you have found it to be located within that code segment (using a profiler or similar tool) 3. you have verified that the compiled code (i. e. the assembler code) actually does what you think it would (it often does not!)

    reply