Bang

gistfile1.txt

/*
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 *
 *   Use lots of bit-ands to duplicate any 1-bits across bytes, then across bits in the last byte
 */
int bang(int x) {
  x = x | (x >> 16); // Now the least-significant byte pair has duplicates of any 1-bits in either byte pair
  x = x | (x >> 8); // Same thing, but by byte
  x = x | (x >> 4); // Same but by nibble
  x = x | (x >> 2); // Now the least-significant pair of bits has 1-bits if any pair in the original x had 1-bits
  x = x | (x >> 1); // The least-significant bit is on if any bits were on in x
  return ~x & 0x1;
}