Learning C bit manipulation

Question

I didn't know any better name for a title of the question.

For ex: on one of my previous questions one answered ((a)-(b))&0x80000000) >> 31 - this is kind of a too advanced for me and i can't really get what it means. I am not looking just for an answer of that, but i need someone to tell me some books/sites/whatever where i can learn this cool "advanced" tricks in C - and learn how and where to use them respectively too.

Answer 1

That's not assembly, it's bitwise arithmetic (wiki). (or this tutorial)

As for when to use it... well, sometimes there are valid uses, but you'll probably already know you need it at that point. That previous answer you mention was given in response to a question where you asked for obfuscation, which ought to give you an idea how necessary it generally is.

Answer 2

Try this link. If it doesn't explain it properly, try googling for "bitwise operation" "bitwise operator" and so on.

link text

Answer 3

Take a look at Expert C Programming

http://www.amazon.com/Expert-Programming-Peter-van-Linden/dp/0131774298/ref=sr_1_1?ie=UTF8&s=books&qid=1268852658&sr=8-1

Answer 4

I have found the following article to be a very clear explanation of bitwise operations -- http://www.gamedev.net/reference/articles/article1563.asp

Answer 5

For bitwise arithmetic, make sure you know binary. Forget the math or converting to and from base 10, but you should know how to deal with hex. (For instance, 00010001 should INSTANTLY flash 11 in your head (This is why people use hex, it's so easy to think in binary).

Note that on your question, the 0x80... number. 8 you should recognize as a power of 2 (1000), and all the other 0's are obviously 0.. so at a glance you should know that it's a long stream of 0's preceded by a single 1 in binary.

You should know how to and/or/not binary numbers and possibly hex at a glance.

0101 & 0011 = 0001, 0101 | 0011 = 0111 should be obvious.  

Slightly less obvious would be the same stuff written in hex:

0x5 & 0x3 = 0x1, 0x5 | 0x3 = 0x7

Also know about shifting. How shifting can double or half the value of a number easily, and how to shift a bitfield around to get what you want.

Work with this stuff for a few weeks and then try to start looking at more binary expressions.

Assembler is another beast altogether, but you'll need to understand binary arithmetic to even begin with assembler.

Edit: (Seeing that you liked my answer, I'll give some bonus content)

I love playing with binary. Try counting to 31 on one hand--count things on TV in binary on your fingers. Write out tables in base 2, 3, 4, 5, ...:

Base: 10    2     3     4     5    ... (Keep going)
      --  ---  ----  ----  ----
       1    1     1     1     1
       2   10     2     2     2
       3   11    10     3     3
       6  110    20    12    11
     ...

Understanding other bases can help you understand binary.

In fact, here's a fun exercise I gave a few people once... One guy actually got it. What's the next number in this sequence:

10, 11, 12, 13, 14, 15, 20, 22, 30, ?

(Since Lars figured it out, I'll put a few more hints in the comments--consider 'em spoilers)

Add, divide, subtract and multiply numbers in binary. Long division in binary works exactly like long division in base 10 but easier. Same with long-form multiplication. Adding a long string of large binary numbers is so easy it's seriously fun!

As you do this kind of operation, you'll start to get an insight into what the CPU does when it manipulates numbers. Realizing how much easier binary is to do than base 10 math should give you a real superiority complex (at least vs stupid CPUs that can't approach the complexity of base 10 and instead just does binary math REALLY FAST to compensate.)

Answer 6

I'd suggest the Writing Great Code Volumes I and II books. All software sits on top of a layer of abstraction. Learning how the layer below you works will give you an immediate and permanent improvement in productivity. For most software engineers this means learning how their computer handles data and executes the instructions the compiler emits. These two books by Randall Hyde are aimed exactly at teaching you these topics.

Answer 7

Hacker's Delight

Topics covered include:

• A broad collection of useful programming tricks
• Small algorithms for common tasks
• Power-of-2 boundaries and bounds checking
• Rearranging bits and bytes
• Integer division and division by constants
• Some elementary functions on integers
• Gray code
• Hilbert's space-filling curve
• And even formulas for prime numbers

Answer 8

If you want to learn about all the weird tricks with bits, Bit Twiddling Hacks is an awesome resource. Some of the tricks there are truly mind-boggling.