bit manipulation tricks(collections)

bithack.cc

/*
 * Reference:
 * http://www.quora.com/Computer-Programming/What-are-some-cool-bit-manipulation-tricks-hacks
 * http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/
 */

#include <iostream>
#include <string.h>

using namespace std;

// print binary representation of an integer
void int_to_bin(int num)
{
  char str[9] = {0};
  int i;
  for (i=7; i>=0; i--)
  {
    str[i] = (num&1) ? '1' : '0';
    num >>= 1;
  }
  cout << str << endl;
}
// (n & 1) test if the first bit is set
bool even(int n)
{
  return ((n & 1) == 0);
}

// Test if the n-th bit is set(0th, 1th, .. nth)
bool nth(int x, int n)
{
  return (x & (1 << n)) != 0;
}

// set the nth bit
int set_nth(int x, int n)
{
  return (x | (1 << n));
}

// unset the n-th bit
int unset_nth(int x, int n)
{
  return (x & ~(1 << n));
}
// Toggle the n-th bit.
int toggle(int x, int n)
{
  return (x ^ (1 << n));
}

// Turn off the rightmost 1-bit
int off_rightmost(int x)
{
  return (x & (x - 1));
}

/*
 * Find out the number of binary 1s in an integer number. native solution below, more efficient using
 * turn off the rightmost 1-bit trick.
 * int count=0;
 * while (n)
 * {
 *   n = n&(n-1);
 *   count +=1;
 * }
 * return count;
 */
int findOnes(int n)
{
  int count = 0;
  while(n)
  {
    count += n&1;
    n >>= 1;
  }
  return count;
}

/*
 * test whether an integer is a power of two.
 */

bool ispower2(int n)
{
  return !(n & (n-1));
}

// isolate the rightmost 1-bit, two possible cases(there is a rightmost 1-bit, and the value is 0)

int isolate(int x)
{
  return (x & (-x));
}

// right propagate the rightmost 1-bit, 01010000=>01011111
int propagate(int x)
{
  return (x | (x-1));
}

// isolate the rightmost 0-bit, 10101011 => 00000100
int isolate0(int x)
{
  return (~x & (x+1));
}

// Turn on the rightmost 0-bit. 10100011 => 10100111
int turn0(int x)
{
  return (x | (x+1));
}

int main()
{
  int_to_bin(10);
  cout << "test even(n): even(-43) = "  << even(-43) << endl;  // 0
  cout << "test nth(x, n): nth(122, 3) = " << nth(122, 3) << endl; // 1
  cout << "test set_nth(x, n), set_nth(16,1) = " << set_nth(16, 1) << endl; // 18
  cout << "test unset_nth(x, n), unset_nth(127, 4) = " << unset_nth(127, 4) << endl; // 111
  cout << "test toggle(x, n), toggle(16, 3) = " << toggle(16,3) << endl; // 10000 => 11000
  cout << "test turn off rightmost 1-bit off_rightmost(x), off_rightmost(00010000) = " << off_rightmost(16) << endl; // 0
  cout << "test Isolate the rightmost 1-bit, isolate(9) = " << isolate(9) << endl; // 1001 => 0001 
  cout << "test power two, 4 is power 2? : " << ispower2(4) << endl;
  cout << "test right propagate the rightmost 1-bit, propagate(12)= " << propagate(12) << endl;
  cout << "test Isolate the rightmost 0-bit, isolate0(3) = " << isolate0(3) << endl; // 0011 => 0100
  cout << "test turn on the rightmost 0-bit, turn0(3)=" << turn0(3) << endl; // 0011 => 0111
  return 0;
}

multiple3.cc

/*
 * If difference between count of odd set bits (Bits set at odd positions)
 * and even set bits is multiple of 3 then is the number is multiple of 3.
 * Reference: http://www.geeksforgeeks.org/archives/511
 */
#include <iostream>
#include <stdlib.h>
#include <math.h>


using namespace std;

// function to check if n is a multiple of 3.

int isMultipleOf3(int n)
{
  int odd_count = 0;
  int even_count = 0;
  if(n < 0) n = -n;
  if(n==0) return 1;
  if(n==1) return 0;
  while(n)
  {
    // if odd bit is set then increment odd count
    if(n&1)
      odd_count++;
    n = n >> 1;
    // if even bit is set then increment even count
    if(n & 1)
      even_count++;
    n = n >> 1;
  }
  return isMultipleOf3(abs(odd_count - even_count));
}

int main()
{
  int num = 22;
  if (isMultipleOf3(num))
    cout << num << " is multiple of 3" << endl;
  else
    cout << num << " is not a multiple of 3" << endl;
  return 0;
}