Bit twiddling for Java or Scala programmers

Does anyone know of good tutorials or even a good book to master bit-level operations? I mean it’s almost clear what every operation does (in Java for instance) or where to find the right documentation, but I’m very new to this topic and I wonder how things like:

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

JavaScript
​x
 
// Find a power of 2 >= initialCapacityint capacity = 1;while (capacity < initialCapacity)    capacity <<= 1;​

work (copied from HashMap). I can’t imagine how Integers, Longs or whatever data type are affected by bit operations 🙁

I mean I don’t want to know every kind of operation, just what seems to be fundamental to high level programmers in Java or Scala like the example provided.

Another example would be:

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JavaScript
 
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions.  This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */static int hash(int h) {    // This function ensures that hashCodes that differ only by    // constant multiples at each bit position have a bounded    // number of collisions (approximately 8 at default load factor).    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}​

That just seems to be magic 🙁

Answer

To understand the basics, you need to understand how data is represented. This requires understanding binary and usually two’s complement.

Once you understand the basics, a lot of useful hacks can be found at the ubiquitous Stanford source.

Advertisement

Answer