Bit Set

One specific usage of bits is to represent sets. Suppose we have a set of N elements {e1, e2, …, en}, and we want to select a subset of K (K <= N) elements. We can use a bit pattern to represent the selection, where 1 indicates the corresponding element is selected, 0 otherwise.

Suppose N=8 and K=4,  we have a bit pattern initialized as 0000 1111, and we want to find the next permutation in lexicographical sense.

The permutations will be,

0000 1111
0001 0111
0001 1011
0001 1101
0001 1110
0010 0111
0010 1011
0010 1101
0010 1110
0011 0011

By looking at the patterns, we can summarize the followings,
1. exclude the trailing zeros, find the least significant zero, change it to one
2. for all the bits after the position, initialized to zeros
3. construct a set of bits with all bits after the bit position found at step 1 to ones, and shift to right by the number of trailing zeros in the original number plus 1

This can be expressed by the code below,

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void prbin(unsigned int x) {

   static char b[65];

   b[0] = '';

   unsigned int z;

   for (z = 0x80000000; z > 0; z >>= 1)

   {

       strcat(b, ((x & z) == z) ? "1" : "0");

   }

   printf("%d=%sn", x, b);

}

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

   int m, n;

   unsigned int x, y, z;

   m = atoi(argv[1]);

   n = atoi(argv[2]);

   printf("permute %d in %d element setn", m, n);

   x = (1 << m)-1;

   while (!(x & (1 << n))) {

       prbin(x);

       y = x | (x-1);      //set all trailing zeros to one

       x = (y+1) | (((~y & -~y) - 1) >> (__builtin_ctz(x) + 1));

   }

   return 0;

}

An alternative method which doesn’t use __builtin_ctz(x) is as below, the comments explains the algorithms briefly.

#include <stdio.h>

 

#include <stdlib.h>

 

#include <string.h>

 

void prbin(unsigned int x) {

 

   static char b[65];

 

   b[0] = '';

 

   unsigned int z;

 

   for (z = 0x80000000; z > 0; z >>= 1)

 

   {

 

       strcat(b, ((x & z) == z) ? "1" : "0");

 

   }

 

   printf("%d=%sn", x, b);

 

}

 

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

 

   int m, n;

 

   unsigned int x, y, z;

 

   m = atoi(argv[1]);

 

   n = atoi(argv[2]);

 

   printf("permute %d in %d element setn", m, n);

 

   x = (1 << m)-1;

 

   while (!(x & (1 << n))) {

 

       prbin(x);

 

       y = x&(~(x-1));   //get the least significant one bit

 

       z = (~x)&(x+y);   //get the least significant zero bit above y

 

       x = x|z;          //set the least significant zero bit above y to 1

 

       x = x&(~(z-1));   //clear all bits after the least significant zero bit above y

 

       x = x | (((z/y)>>1) - 1); //appending the ones

 

   }

 

   return 0;

 

}

 

Save the code to bitsets.c and bitsets2.c. Compile the code using the commands below,

gcc -o test bitsets.c

gcc -o test2 bitsets2.c

Below are some sample executions,

./test 3 5

permute 3 in 5 element set

7=00000000000000000000000000000111

11=00000000000000000000000000001011

13=00000000000000000000000000001101

14=00000000000000000000000000001110

19=00000000000000000000000000010011

21=00000000000000000000000000010101

22=00000000000000000000000000010110

25=00000000000000000000000000011001

26=00000000000000000000000000011010

28=00000000000000000000000000011100

./test2 3 5

permute 3 in 5 element set

7=00000000000000000000000000000111

11=00000000000000000000000000001011

13=00000000000000000000000000001101

14=00000000000000000000000000001110

19=00000000000000000000000000010011

21=00000000000000000000000000010101

22=00000000000000000000000000010110

25=00000000000000000000000000011001

26=00000000000000000000000000011010

28=00000000000000000000000000011100

References
1. http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation