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 - 2 years, 2 months ago

    Nice..added your link to our resources page!

    reply

  • Cure Panic Attacks fast - 5 days, 17 hours ago

    I tag it to my most love’s web webpage rundown and will be returning soon. Kindly look at my site additionally and let me comprehend what you ponder Panic Away.

    reply

  • Best Affiliate Program 2015 - 5 days, 17 hours ago

    This really is truly an amazing read for me personally. Much appreciated to you just for distributed content having an exceptional understanding consolidates me to check on all the more frequently for new expound on Google Sniper.

    reply

  • Sleeping Tablets Online - 1 day, 2 hours ago

    This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article.

    reply

  • Herve - 2 years, 2 months ago

    Cool tricks!

    reply

  • Caverna - 2 years, 2 months ago

    It's great to PIC programming...

    reply

  • D - 2 years, 2 months ago

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

    reply

  • Agentlien - 2 years, 2 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 - 2 years, 2 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

  • education news - 2 months, 3 weeks ago

    This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article.

    reply

  • boom beach cheats - 2 months, 2 weeks ago

    I’ve been searching for some decent stuff on the subject and haven't had any luck up until this point, You just got a new biggest fan!..

    reply

  • Estimular al bebé - 3 days, 16 hours ago

    The website is looking bit flashy and it catches the visitors eyes. Design is pretty simple and a good user friendly interface.

    reply

  • Best University in Vietnam - 13 hours ago

    I really appreciate the kind of topics you post here. Thanks for sharing us a great information that is actually helpful. Good day!

    reply

  • mspy coupon code 2015 - 1 week, 4 days ago

    Someone Sometimes with visits your blog regularly and recommended it in my experience to read as well. The way of writing is excellent and also the content is top-notch. Thanks for that insight you provide the readers!

    reply

  • stefan - 2 years, 2 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

  • subway surfers hack - 2 months, 2 weeks ago

    Very good written article. It will be supportive to anyone who utilizes it, including me. Keep doing what you are doing – can’r wait to read more posts.

    reply

  • sports orthotics - 2 months, 1 week ago

    Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too. There tend to be not many people who can certainly write not so simple posts that artistically. Continue the nice writing

    reply

  • buy likes - 2 months ago

    This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post!

    reply

  • get pinterest followers - 2 months ago

    You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant!

    reply

  • how to have more followers on instagram - 1 week, 5 days ago

    I read your blog frequently and I just thought I’d say keep up the amazing work!

    reply

  • buy comments on instagram - 1 week, 5 days ago

    Hello There. I found your blog using msn. This is an extremely well written article. I will be sure to bookmark it and return to read more of your useful information. Thanks for the post. I’ll certainly comeback.

    reply

  • snapdeal promo codes - 6 days, 4 hours ago

    I wonder if it would be worth it to systematically use Ctype all the time. Like a new way to program python.

    reply

  • http://neueseoservices.ca/ seo company - 6 days, 1 hour ago

    On my website you'll see similar texts, write what you think.

    reply

  • Denver - 6 days ago

    You have even managed to make it understandable and easy to read. You have some real writing talent. Thank you.

    reply

  • moving companies charlotte nc - 5 days, 23 hours ago

    I came onto your blog while focusing just slightly submits. Nice strategy for next, I will be bookmarking at once seize your complete rises...

    reply

  • Get Pregnant fast - 5 days, 17 hours ago

    I believed it was likely to be a few exhausting aged post, however it really made up regarding my period. I will existing a connection about this page upon my internet journal. Almost certainly my visitors will location that significantly suitable regarding Pregnancy miracle.

    reply

  • Buy Google Plus Followers - 5 days, 2 hours ago

    I would like to say that this blog really convinced me to do it! Thanks, very good post.

    reply

  • how to get free gems in clash of clans - 5 days ago

    Awesome and interesting article. Great things you've always shared with us. Thanks. Just continue composing this kind of post.

    reply

  • hay day mod apk - 5 days ago

    Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that "The content of your post is awesome" Great work.

    reply

  • Ginefiv - 4 days, 16 hours ago

    This was a really great contest and hopefully I can attend the next one. It was alot of fun and I really enjoyed myself..

    reply

  • Loft conversions South London - 3 days, 23 hours ago

    That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more.

    reply

  • Refresh Cosmetic & Laser Clinic Brisbane - 3 days, 17 hours ago

    This is very significant, and yet necessary towards just click this unique backlink:

    reply

  • Mazda dealership las vegas - 3 days, 2 hours ago

    Thank you very much for posting and sharing this great article. It is so interesting. I want to know some other information about this site. So please give me this news quickly. I always will be aware of you.

    reply

  • Salesforce Training in Chennai - 2 days, 21 hours ago

    Thanks for this article on Bit Level Manipulation. Very informative one.

    reply

  • Wedding Hair Comb New York - 2 days, 19 hours ago

    I also wrote an article on a similar subject will find it at write what you think.

    reply

  • internet marketing services - 2 days, 18 hours ago

    Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts.

    reply

  • electronic gadgets - 2 days, 4 hours ago

    I like the way in which you have designed your blog. It is very easy to read and see. Will you please update more posts for helping your visitors

    reply

  • Richard A Kimball - 1 day, 5 hours ago

    Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post .

    reply

  • Richard A Kimball - 1 day, 4 hours ago

    Awesome and interesting article. Great things you've always shared with us. Thanks. Just continue composing this kind of post.

    reply

  • Best university in Vietnam - 1 day, 4 hours ago

    I do believe all the concepts you’ve introduced to your post. They’re very convincing and can definitely work.

    reply

  • west palm beach hard drive data recovery - 1 day, 4 hours ago

    Thank you for this post. Thats all I are able to say. You most absolutely have built this blog website into something speciel. You clearly know what you are working on, youve insured so many corners.thanks

    reply

  • need more money - 15 hours ago

    Really a great addition. I have read this marvelous post. Thanks for sharing information about it. I really like that. Thanks so lot for your convene.

    reply

  • How to Buy Sleeping Tablets Online - 5 hours ago

    It’s better to take proper diet so to add necessary nutritious elements in daily meal. Take proper exercise which is suitable during this stage.

    reply