GP2X Interesting Bit Of Logic/maths/code Needed For Binary Problem

[Parkydr]

Here's another solution - cycle combinations of n bits

Pros: Less values to check
Cons: recursive function calls

I think we can safely say that this is the current leader. I couldn't get Gueben's to work properly - I just get junk out and it gets into infinite loops and all sorts. It's probably fixable, however. I didn't try the pre-computed tables ones because I would probably have to use Parkydr's algorithm to pre-compute them anyway!

On a 2GHz dual-core, my algorithm takes a big hit around the 300-340th iteration (i.e. the 340th number with 2 bits in its binary representation). It takes 18s of CPU time to get to 400. Parkydr's does it in 0.012s.

Whacking it up to the largest thing that a "long long" can handle (the 1953'th iteration), my algorithm probably wouldn't finish this side of Christmas... 2020. Parkydr's exhausts that within 0.09s. Making it do tons of different ones with different numbers of bits, I couldn't make it hit a second of computation time.

Those numbers are with unoptimised code, with the same number of printf's (which probably slow Parkydrs down a lot in comparison because it can barely write to the screen fast enough, while mine you can see the individual lines pop up on the screen one at a time after the 250th iteration).

The numbers scale in similar ways for other numbers of bits, so I think it's safe to say that Parkydr is currently out in front with his amazing recursive algorithm (I will have to check stack usage of such a thing, though, but to be honest, if I have to make a "fake stack" in RAM, it's worth it) which is orders of magnitude better than the naive example.

It's not that I don't trust you, Parkydr, but I have also double-checked the figures against my naive example to make sure that they are in fact correct and they appear to be.

Any other contenders or shall we all just beat Parkydr up?



You may crown me 1337 h4x0r now

The stack shouldn't be a problem, in only recurses n (number of bits) deep.

 

[Adventus]

Hmm looks like i came up with something similar to paeryn and Trevor. It should work in general (unless x = 0):
Some cpu architectures (ie X86) have an instruction to do the integer log2 function.
CODE
//fast log2 provided by wikipedia:
int fastlog2(unsigned int n) {
int pos = 0;
if (n >= 1<<16) {n >>= 16; pos += 16;}
if (n >= 1<< 8) {n >>= 8; pos += 8;}
if (n >= 1<< 4) {n >>= 4; pos += 4;}
if (n >= 1<< 2) {n >>= 2; pos += 2;}
if (n >= 1<< 1) {pos += 1;}
return ((n == 0) ? (-1) : pos + 1);
}

unsigned int next_binary_string_with_x_bits(const unsigned int start, unsigned int x){

int r = 1;
if (start){
//find dimensions of 'start'.
int dim;
//frexp(start, &dim); //floating point (int)log2. Might be faster.
dim = fastlog2(start);

//find least significant 01 pair within starts dimensions:
int d = dim;
int l = 1;
int u = 2;
while(--d){
if ((start & l) && !(start & u)){
return ((start ^ l) ^ u);
}
l = u;
u <<= 1;
}

//if one doesn't exist, increase dim:
r = (1 << dim + 1 - x);
}

while(--x){r = (r << 1) | 1;}
return r;
}


Edit: PS I haven't tested it much, just checked a few of the values you provided.

 

[Geuben]

It seemed to struggle with the loop:

while(((start >> 1) % 2) == 0)

which ends up hanging in an infinite loop with start=0. I was wondering if there was supposed to be a >>= instead and tried several combinations but everything I tried didn't work or just looked completely wrong. If I did get answers, they were immediately nonsense. I know the basic idea works, because I was toying with it myself before, but there's probably a tiny logical error in that code somewhere that blows things up.

snip

Ah, starting from zero will probably be the problem, start >> 1 bitshifts start right by one place, % 2 is modulus 2 (i think) and the ==0 is to check the remainder is 0.

Basically that while loop is supposed to run until the least significant bit of start is 1.

I had a think about it some more and I'm pretty sure there are some more mistakes in the implementation anyway.

 

[gbouilland]

@Trevor Bradley : That's exactly the way I tackled this problem which end up with a regexp doing the deed

 

[azmodean]

okay, here's a solution inspired by Guben's idea, but basically all with bit-shifting. Not sure how it stacks up agains the other contenders, but it's pretty fast. O(n) where n is number of digits till the first 0 following a 1, also cache-able I think

CODE

#include "stdio.h"


/*
PRE: start is a number to permute or 0,
x is nmber of 1's in binary representation of number

if start is 0, return smallest number with appropriate number of bits set
otherwise find next larger number with same number of bits set

method:
find smallest set bit with an unset bit after it
all preceeding (contiguous) set bits (if any) are moved to start
target bit is shifted up by 1
*/


unsigned int next_binary_string_with_x_bits(unsigned int start, int x)
{
printf("start = %u, x = %u\n", start, x);
if(0 == start)
{
return ~ (0xFFFFFFFF << x);
}
else
{
unsigned int i = 0, n = 0;
/*assuming start has correct number of bits set, otherwise this will not work, shouldn't crash or infinite loop though*/
/*find position of lowest order set bit */
while(! (1 << i & start) )
{
i++;
}
i++; /*advance to next index before counting 1's*/
/*if i is >= sizeof (start - x), either invalid input or we've reached largest number*/
if (i == 8)
{
return 0;
}
while(1 << i & start)
{
i++;
n = (n << 1) | 1;
}

/*now i is the index of a 0 bit that should be set, and n is a number with bits set at the start*/
/*once again, if j > x or if i >= sizeof start, we have invalid input or we've reached the largest number*/
return (start & 0xFFFFFFFF << i) | 1 << i | n;
}
}

int main()
{
unsigned int num = 0, digits = 3;
while (num = next_binary_string_with_x_bits(num, digits))
{
printf("current number is %u\n", num);
}
printf("last number is %u\n", num);
return 1;
}



EDIT: compiled, run, and briefly checked for correctness of output.
EXIT X2: gah, almost the same as payern's implementation, I skimmed through the thread and his solution didn't look like what I was thinking of at first, but while I was implementing it it shifted (pun intended) to match his.

 

[M-HT]

I decided to really stress the implementations so I tested them with x=16 up to 100000 iterations on my PC.
Results:
Adventus: returned wrong result in 34th iteration (meaning the rest was also wrong) - not timed (wrong in the sense that the result did have 16 1's, but it was higher then the correct result)
parkydr: almost 4 minutes
paeryn, azmodean, and my implementation: cca 1 second

Next step: 1000000 iterations.
Results:
azmodean: returned 0 in cca 245170th iteration
after increasing the constant in line CODE
if (i == 8)
it worked again
parkydr: not timed
paeryn, azmodean, and my implementation: cca 2 seconds

P.S.
My implementation can be found here:
next_binary_string_with_x_bits.c - version for 32-bit numbers
next_binary_string_with_x_bits64.c - version for 64-bit numbers

Edit:
I forgot to write, that my implementation solves more general problem - for any starting number it returns nearest higher number with x number on 1's

 

[Klepto]

In Forth (could possibly be optimised and tidied)...
CODE
hex
020 constant WORD-SIZE
: saturate-bits ( count -- u ) 0 swap 0 ?do 1 i lshift or loop;
: set-pattern ( u1 position -- u2 ) dup 3 swap lshift invert rot and swap 2 swap lshift or;
: go ( start -- next )
0 swap WORD-SIZE 1- 0 do
dup i rshift 3 and
dup 1 = if drop i set-pattern i saturate-bits invert and swap saturate-bits or leave
else 3 = if swap 1+ swap then then
loop;


In pseudocode...
CODE
loop over bits
if next 2 bits = 01 then
change bits to 10
right align all bits less significant than the pattern
break
else
if next 2 bits = 11 then increment bit counter
end
end


It seems to work, is this what we're after? (in binary)
CODE
01010101 ok
go dup u. 1010110 ok
go dup u. 1011001 ok
go dup u. 1011010 ok
go dup u. 1011100 ok
go dup u. 1100011 ok
go dup u. 1100101 ok
go dup u. 1100110 ok
go dup u. 1101001 ok
go dup u. 1101010 ok
go dup u. 1101100 ok
go dup u. 1110001 ok
go dup u. 1110010 ok
go dup u. 1110100 ok
go dup u. 1111000 ok

 

[Adventus]

QUOTE
Adventus: returned wrong result in 34th iteration (meaning the rest was also wrong) - not timed (wrong in the sense that the result did have 16 1's, but it was higher then the correct result)
Haha, i knew my code was fishy... was quite surprised it worked at all. .

Heres probably the fastest implementations of the "find next number with same number of bits" algorithm : http://www.hackersdelight.org/HDcode/snoob.c

@Klepto: I think most of our implementations are based on that idea. Finding the least significant 01 pair and swapping it to 10.

 

[Klepto]

@Klepto: I think most of our implementations are based on that idea. Finding the least significant 01 pair and swapping it to 10.

Yeah, I know. I felt I needed to include something as not many here will read Forth.

 

[azmodean]

Heres probably the fastest implementations of the "find next number with same number of bits" algorithm : http://www.hackersdelight.org/HDcode/snoob.c




Nice find, now that one of the comments in that code pointed out that this can be used as an algorithm for "selecting each subset of size x from a set of size y where y > x", I'll be stashing it somewhere in case I need it in the future

On another note, I don't feel bad at all about not thinking of the the "smallest = x & -x" method for finding the lowest order set bit, my brain just doesn't work that way

 

[Crazyace]

If the input number has x bits already I'd use this way:

;Lowest bit set , if you want 128 bit math -n = ^n+1 , so carry can be n==0 test per word

b1 = n & ( -n )

;Set all trailing 0's to 1's

n1 = n | (b1-1 )

;Complement

n1 = ~n1

;Now find lowest set bit in complement ( lowest clear bit in number that isnt trailing )

b0 = n1 & (-n1)


;Now to find the next highest , we clear the lowest set bit, and set the lowest (internal) clear bit

n = n ^ b1 ^ b0


That should work ( it's only my scribblings though )