find all 'n'-bit numbers with 'k' bit set [modified]
-
Hello Everybody, suppose A = number of ones B = number of zeros C = A + B now there will be total of X unique C-bit numbers in which A bits are 1 and B bits are 0 X = (C!) / (A! * B!) example A = 4 B = 2 C = 6 X = 6! / (4! * 2!) = 15 01 001111 02 010111 03 011011 04 011101 05 011110 06 100111 07 101011 08 101101 09 101110 10 110011 11 110101 12 110110 13 111001 14 111010 15 111100 now, is there any algorithm by which we can find values of these X C-bit numbers with out going through each of C-bit numbers i.e without using following method
for(i = 0; i < pow(2, C); ++i)
{
if i contains A 1s and B 0s then add i to list
}thanks.
My Blog.
My codeproject Articles.modified on Saturday, July 2, 2011 5:52 AM
-
Hello Everybody, suppose A = number of ones B = number of zeros C = A + B now there will be total of X unique C-bit numbers in which A bits are 1 and B bits are 0 X = (C!) / (A! * B!) example A = 4 B = 2 C = 6 X = 6! / (4! * 2!) = 15 01 001111 02 010111 03 011011 04 011101 05 011110 06 100111 07 101011 08 101101 09 101110 10 110011 11 110101 12 110110 13 111001 14 111010 15 111100 now, is there any algorithm by which we can find values of these X C-bit numbers with out going through each of C-bit numbers i.e without using following method
for(i = 0; i < pow(2, C); ++i)
{
if i contains A 1s and B 0s then add i to list
}thanks.
My Blog.
My codeproject Articles.modified on Saturday, July 2, 2011 5:52 AM
Never use pow(2,someint). It's inaccurate and slow. You might as well do
1<<someintAnd yes, there is such an algorithm, you can quickly generate the next bit-permutation[^]. Just start out with(1<<k)-1and keep using that permutation function until you have them all. -
Never use pow(2,someint). It's inaccurate and slow. You might as well do
1<<someintAnd yes, there is such an algorithm, you can quickly generate the next bit-permutation[^]. Just start out with(1<<k)-1and keep using that permutation function until you have them all.thanks david.