1. Snafuist, please explain exactly how negating the input and then computing the number of trailing zeroes would give the answer. Do you mean to say that a further modification of the method of computing the number of trialing zeroes outlined on your webpage would give the answer? As far as I can tell, there is no requirement that the first 1 bit will only be followed by 1 bits, thus merely computing the number of trialing zeroes of the bitwise negated value is not guaranteed to give the correct answer. 2. If you're going to use a lookup table (which is probably a good idea) then I'd go with an array of chars rather than an array of ints. The reduction in space by a factor of four has surely got to make up for the single promotion to integer after the array access. 3. Originally Posted by iMalc
If you're going to use a lookup table (which is probably a good idea) then I'd go with an array of chars rather than an array of ints.
I was thinking more of an array of unsigned char. 4. Originally Posted by quzah Yeah, I can do it in 1 with a lookup table. But your lookup table will waste memory, as it will have 256 entries.

Here's a proof-of-concept code that does (not quite) exactly what the OP wanted to achieve:

Code:
```int ffc(char c)
{
c = ~c;

static const char debruijn = {0, 1, 2, 4, 7, 3, 6, 5};
return debruijn[((c & -c) * 23) >> 5];
}```
It is full of magic numbers and without reading the HOWTO, it will be very hard to understand what the code is doing.

Greets,
Philip 5. Originally Posted by iMalc If you're going to use a lookup table (which is probably a good idea) then I'd go with an array of chars rather than an array of ints. The reduction in space by a factor of four has surely got to make up for the single promotion to integer after the array access.
Yes, that was my silly example. If I was actually programming this myself I think that would have occurred to me (unsigned char) -- hopefully it will to the OP as well. 6. As far as I can tell, there is no requirement that the first 1 bit will only be followed by 1 bits, thus merely computing the number of trialing zeroes of the bitwise negated value is not guaranteed to give the correct answer.
Oops, you're right. I concluded that from his examples, but it is certainly not a requirement. In this case, my solution is crap :-)

Greets,
Philip 7. Originally Posted by MK27 Gosh tabstop, that is a pretty hard objection to object to.
You mean other than the fact that it's wrong? There aren't any trailing zeros, which means the first channel is available. Try it yourself:
Code:
```#include<stdio.h>
int main ( void )
{

unsigned int v = 1 + 4 + 16 + 64;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int debruijn =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = debruijn[((v & -v) * 0x077CB531UL) >> 27];

printf( "%d", r );

return 0;
}```
Should display zero, because there are no zeros. Otherwise, if you drop the "1 +", you'll get 2.

Quzah. 8. Originally Posted by Snafuist
Here's a proof-of-concept code that does exactly what the OP wanted to achieve:
A quick test shows that it returns the wrong results for inputs of 3 and 255. 9. Originally Posted by Snafuist But your lookup table will waste memory, as it will have 256 entries.
Now you're just adding more requirements. First you said "can you do it in less", but now you're saying "no, I meant instead of less operations, less memory!"

You can have less memory, or less operations. You have to pick one. That's just the way things work. The fewer operations you use, generally you end up using more memory.

Quzah. 10. Originally Posted by quzah You mean other than the fact that it's wrong? There aren't any trailing zeros, which means the first channel is available. Try it yourself:
Code:
```#include<stdio.h>
int main ( void )
{

unsigned int v = 1 + 4 + 16 + 64;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int debruijn =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = debruijn[((v & -v) * 0x077CB531UL) >> 27];

printf( "%d", r );

return 0;
}```
Should display zero, because there are no zeros. Otherwise, if you drop the "1 +", you'll get 2.

Quzah.
And? According to the "algorithm" (subtract the number of trailing zeroes from 9), that means that the first available channel is channel 9 which isn't right. 11. Originally Posted by quzah Now you're just adding more requirements. First you said "can you do it in less", but now you're saying "no, I meant instead of less operations, less memory!"
You're of course right, I should have been more explicit. A full lookup table is the most time efficient way to do it.

Greets,
Philip 12. Originally Posted by tabstop And? According to the "algorithm" (subtract the number of trailing zeroes from 9), that means that the first available channel is channel 9 which isn't right.
No it doesn't. Change v to nine. Go on, do it. Put it in and it returns 0. Why? Because it returns 0 for anything with the first bit set.

Quzah. 13. Originally Posted by quzah No it doesn't. Change v to nine. Go on, do it. Put it in and it returns 0. Why? Because it returns 0 for anything with the first bit set.

Quzah.
Good. That's what it's supposed to do. Here's my claim:
1. The original input is 10101010 (which has a first open channel # of 1).
2. The bit reversal is then 01010101.
3. There are no trailing zeroes in this number (as the code above exemplifies and which no one is disagreeing with).
4. Therefore, according to the proposed solution, there are no available channels (since the next available channel was supposed to be given by 9 - the answer to part 3, which here is 0). 14. I think we can stop discussing Snafuist's suggestion now as Snafuist has admitted that it is based on an unwarranted assumption. 15. Originally Posted by laserlight I think we can stop discussing Snafuist's suggestion now as Snafuist has admitted that it is based on an unwarranted assumption.
But I don't think it actually is wrong. I think the description of it is wrong. Pass it any number, and it should produce the place of the first set bit. Try it. Set it up in a loop, and display the bits for that value, as well as the number it returns. Heck, I'll do it:
Code:
```#include<stdio.h>
void printbit( unsigned char b )
{
printf( "%d%d%d%d%d%d%d%d ",
!!(b & 1),  !!(b & 2),
!!(b & 4),  !!(b & 8),
!!(b & 16), !!(b & 32),
!!(b & 64), !!(b & 128) );
}
int main ( void )
{
size_t counter;
unsigned int v = 0; /* 1 + 4 + 16 + 64; */
int r;
static const int debruijn =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

for( counter = 0; counter < 255; counter++ )
{
v = counter;
r = debruijn[((v & -v) * 0x077CB531UL) >> 27];

printf( "%d:" , r );
printbit( counter & 0xFF );
printf( "\n" );
if( counter % 8 == 7 )
getchar( );
}

return 0;
}```
I don't think it's wrong, I think it's being misrepresented in its functionality, or how it should be used. I'm not seeing anything wrong with the way it's actually functioning. Pass it a number, it will tell you the place of the first set bit.

The only exception is if you pass it zero, which it returns zero for as well. So as long as you check your passed value to see if it is zero, you're fine.

Quzah. Popular pages Recent additions 