Thread: I want to get good with bitwise stuff

1. I want to get good with bitwise stuff

There is a bit of untapped power in my current C programming skills. I dive into bit manipulation here and there, but there are guys I work with who are machines with it... They can write a program that other people wrote in 50 lines of loops, if statements, and more in 1-5 lines of some cool bit manipulation stuff.

I'm not saying this style should always be done, but there are times where it's necessary. Sometimes it blows my mind how much can be done with the bitwise operators and bit flipping. I want to improve at this but unfortunately, I haven't really figured out how to do it because the types of programmers I work with rarely use this low-level stuff. I feel like if I was put into an embedded shop, I would have to learn, but short of having to switch jobs, how else would you recommend getting much better with bit fields, bitwise operators, and the like?

One thing I have tried on occasion is sitting down with a pen and paper and just manually working through bitwise operations in binary. It's been fun and educational so far, but haven't had to do it quite enough to get fluent.

2. You can start here: Bit Twiddling Hacks

Note that not everything there is portable or even necessarily faster than what a modern C compiler on a modern CPU would produce, but, hey, gotta start somewhere

3. Also, there is this good book: Hacker's Delight

4. I should also add that if you can't already do it, teach yourself to convert hexadecimal to binary in your head (and vice versa); this is easy because each hex digit (0-F) is only 4 binary digits and being able to do so makes reading and reasoning about bitwise stuff a lot easier in some circumstances. Be able to, using paper at least, add, subtract, multiply etc numbers no matter what their base is (but starting with hexadecimal and binary arithmetic is probably sufficient)

Read about things like one and two complement representation of signed numbers
Understand why x & 1 can be used to determine if a number is odd or even and work your way up to more complex stuff

5. Thank you for the suggestions. I've been reading some of the Hacker's Delight book. The mathematical notation is a bit tough for me to "convert to code" in my brain so-to-speak. However, the semantics and code sections make sense.

While on this topic, I have a question:

It seems as though in computer science, we care more about these "on and off switch" usages of binary numbers more than the actual values of them numbers... For example, say I have the number:

0b1011

The "value" of this number is decimal 11.

Likewise:

0b1001 0110 - Value is decimal 150

However, with bit manipulation techniques, the above 2 binary numbers may instead be seen as 4 switches in the first example followed by 8 switches in the second example. Here, we are less concerned about the decimal value that the number holds, and more concerned about whether or not each individual binary digit is set (1) or clear (0).

To give a final illustration, say we have the number above:

0b1001 0110

We want to set the second-to-highest bit to 1 like this:

0b1101 0110

We can do this:

0b1001 0110
OR
0b0100 0000
=
0b1101 0110

0100 0000 happens to hold the value of decimal 64. My question is: Is there any significance to the fact that the number we had to use to set that bit happens to be 64? In decimal, we performed 150 OR 64 to get 214. We added 64 to the value of 150 which creates the number 214.

Is it beneficial as a programmer or computer scientist to look at the decimal values of these bitwise interactions, or is there no real use in that, and instead, they should be viewed simply as position bit flips to store switches?

6. One thing I've learned so far is that the seemingly complex bitwise stuff, when worked through step-by-step becomes much clearer as to the big picture of "what is going on."

I realized that something such as taking a 32-bit number and swapping byte 2 with byte 4 for example, ends up being several shift, and, or operations that look complex, but when broken down, it's just "swap byte 2 and 4 of a word" basically...

I took all of the advice here and I am currently reading Hacker's Delight plus I memorized the Decimal->Hex->Binary conversions... I'm working on visualizing each hex digit with corresponding bits which helps understand what the various bitwise operators are doing.

As a side note, it seems that AND and NOT and OR and NOT are powerful combinations of operators... It also seems that XOR with all 1 bits or FFFF is almost the same as NOT operation.