I need help on Bit Twiddling

Question

I love to see people writing Bit Twiddling code but I just can't understand it at all. Gone through Hacker's Delight and http://graphics.stanford.edu/~seander/bithacks.html, but I failed to understand anything.

For example:

How come 1 | 2 returns 3 or how come a ^=b; b ^= a; a ^=b; swap the values etc...

One method:

private T[] ensureCapacity(int minCapacity) {
   if (tmp.length < minCapacity) {
   // Compute smallest power of 2 > minCapacity
   newSize |= newSize >> 1;
   int newSize = minCapacity;
   newSize |= newSize >> 2;
   newSize |= newSize >> 4;
   newSize |= newSize >> 8;
   newSize |= newSize >> 16;
   newSize++;

    if (newSize < 0) // Not bloody likely!
      newSize = minCapacity;
    else
      newSize = Math.min(newSize, a.length >>> 1);

      @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
      T[] newArray = (T[]) new Object[newSize];
      tmp = newArray;
   }
   return tmp;
 }

What the below likes are doing:

int newSize = minCapacity;
newSize |= newSize >> 1;
newSize |= newSize >> 2;
newSize |= newSize >> 4;
newSize |= newSize >> 8;
newSize |= newSize >> 16;
newSize++;

or

newSize = Math.min(newSize, a.length >>> 1);

Better to use >> or >>> operator I mean after Joshua Bloch fixed the broken binary search I understand that it's safe to use >>> instead >>. Please help and if there is a tutorial then the above mentioned source I will appreciate that very much.

What is the easiest way to calculate the output of bits for example 1 | 2 = 3?

I mean I don't know how the bit form looks except I use a calculator or something.. Is there any easiest way to calculate these things without any help but in mind?

You appear to be asking for a tutorial or something, rather than a solution to a specific problem. You will get a couple of things here, but for a more complete package, try The Art of Computer Programming chapter 7.1.3 and Hacker's Delight. — harold, May 14 '13 at 18:44

score 1 · Answer 1 · answered May 14 '13 at 17:31

1

What is the easiest way to calculate the output of bits for example 1 | 2 = 3.

Write out the numbers as binary. This is how the numbers are really represented.

  00000001
| 00000010
= 00000011

answered May 14 '13 at 17:31

Peter Lawrey

525,659
79
751
1,130

How about quake square root algorithm? That is reliable for just playing games or glitchy? – huseyin tugrul buyukisik May 14 '13 at 17:32
@huseyintugrulbuyukisik I assume you mean http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ I believe it good enough for games. Given all the other unrealistic things going on, I suspect it makes no difference. – Peter Lawrey May 14 '13 at 17:35
@huseyintugrulbuyukisik NO not the quake square root algo I was looking for basis not that advance.. Thanks.. ;) – Destiny Awaits May 17 '13 at 16:06
In short, the reason it works is because the start of the number is a an exponent, and get a sqrt of a log of a number is just divide by 2 (or shift by 1) This forms a starting approximation for a newton approximation of a sqrt. If you did a second iteration of this, the result would be more accurate (but slower). – Peter Lawrey May 17 '13 at 20:57

score 1 · Answer 2 · edited May 14 '13 at 18:11

You're gonna have to study a little, but here's a little cheat sheet to know the number in binary form

128 | 64 | 32 | 16 | 8 | 4 | 2 | 1

If you want 3, go from left to right, filling up in the spaces that contains the values you need to create the number 3

128 | 64 | 32 | 16 | 8 | 4 | 2 | 1
                             X   X

2 + 1 = 3 so you replace the ones marked with X with 1s and the rest with 0s

00000011

The same for the number 2:

128 | 64 | 32 | 16 | 8 | 4 | 2 | 1
                             X

And the binary result is.

00000010

For the number 47:

128 | 64 | 32 | 16 | 8 | 4 | 2 | 1
            X        X   X   X   X

Binary result:

00101111

This is not a rule, or formula or anything. It's just something to help you convert numbers a little faster, and practice it in your head. You'll still need to study a lot if you want to play with bits :-)

@askewchan I find the above explanation very helpful. One thing I wanted to know are there any more advance tricks this easy or a bit up level I will try to read and work on to improve my skills.. Thanks... :) — Destiny Awaits, May 17 '13 at 16:05

I need help on Bit Twiddling

2 Answers2

Linked