bit-twiddling for do combination

/* This program accepts n and k on the command line, then prints
* all n C k combinations of integers from 1..n
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
        int     n, k, i, j, c;

        if (argc != 3) {
                printf ("Usage: %s n k\n", argv[0]);
                exit (1);
        n = atoi (argv[1]);
        k = atoi (argv[2]);

    /* i goes through all n-bit numbers */

        for (i=0; i<(1<<n); i++) {

        /* masking the j'th bit as j goes through all the bits,
         * count the number of 1 bits.  this is called finding
         * a population count.
                for (j=0,c=0; j<32; j++)
                    if (i & (1<<j))

        /* if that number is equal to k, print the combination... */
                if (c == k) {

            /* by again going through all the bits indices,
             * printing only the ones with 1-bits
                     for (j=0;j<32; j++)
                          if (i & (1<<j))
                               printf ("%i ", j+1);
                      printf ("\n");

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s