Bit Manipulation

Bitwise operations are a very weak spot for me. ANDing, ORing, and XORing (huh?) bits hasn't really been anything I can say I've needed to do, except for one company that used bitfields to save space. And << and >> have had little practical use for me.

By the end of the day, these will all be second nature. I'll be shifting and ^= with no problem.

To start myself off right, I made a method to show the bit representation of any word size:

void btoa(char bits, char *output, int size);

int main(int argc, char* argv[]) {

  const int size = sizeof(unsigned int) * 8;

  for (unsigned int i = 0; i < 20; ++i) {
    char buffer[size + 1] = {0};
    buffer[size] = '\0';
    btoa(i, buffer, size);
    printf("%3d: %s\n", i, buffer);
  }

  return EXIT_SUCCESS;
}

void btoa(char bits, char *output, int size) {  
  for (int i = size - 1; i >= 0; --i, bits >>= 1) {
    output[i] = (char)('0' + (bits & 1));
  }
}

I found this video to be especially useful:

Today's studies are going extremely well. I've put together this Hamming distance algorithm uses the Hamming Weight (Kernighan method, first discovered by Wegner) to count bits that differ once I've XORed the values:

def hamming_distance(x, y):  
    difference = x ^ y
    count = 0
    while difference != 0:
        count += 1
        difference &= difference - 1
    return count
comments powered by Disqus