Bitwise Operations

It's fairly convoluted though very efficient to encode lots of pieces of Boolean information into a single integer variable. Normal arithmetic and logical operations on such integer variables become unintuitive since we're not usually concerned with the value of the variables (e.g., 17) but rather with the status of individual bits (say, the first and fifth bits are set, all other bits are unset).

This page presents some bitwise operations I found useful while writing an extremely CPU-intensive ray-tracer. C syntax is used but the techniques can be applied to other languages including Java, often with only minor syntax changes.

Tests

• Is a power of two:
  
      v & (v-1) == 0
  
  
  

• Has two or more set bits:
  
      v & (v-1) > 0
  
  
  

• Has exactly one set bit:
  
      v && (v & (v-1) == 0) == true
  
  
  

• Has all specified bits set:
  
      v & bits == bits
  
  
  

• Has at least one specified bit set:
  
      v & bits > 0
  
  
  

Operations

• Toggle specific bits:
  
      v ^= b;
  
  
  

• Set a bit:
  
      v |= b;
  
  
  

• Unset a bit:
  
      v &= ~b;
  
  
  

• Unset all bits apart from lowest set bit:
  
      ((v ^ (v-1)) + 1) >> 1
  
  
  

• Unset the lowest set bit only:
  
      v &= (v-1)
  
  
  

Other

• Count number of set bits:
  
      int n = 0; if (v) do { n++; } while (v &= (v-1)); return(n);
  
  
  

• Compute log2 of a power of two:
  
      float x=v; return (*(int*)&x >> 23) - 127;
  
  
  

• Compute minimum of two signed 32-bit integers:
  
      j + (((i-j) >> 31) & (i-j))