Bitwise Op

🦥 An old note.

Bitwise vs Arithmetic

running on a vector of size 2^31, bitwise operations are significantly faster than arithmetic counterparts:

  seg = 64;
  volume = (vec_size - 1)/ seg + 1;
  unsigned bs = log2(seg);
  unsigned bv=  log2(volume);
  unsigned bbv = volume - 1;

Arithmetic: out[i] = i % volume * seg + i / volume

Bitwise: out[i] = ((i & bbv) << bs) + (i >> bv)

The time difference: