Show 80 post(s) from this thread on one page
Page 4 of 6 First 123456 Last
• 05-28-2009
tabstop
Quote:

Originally Posted by quzah
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:

At the risk of incurring the wrath of the mods:

I ran the code you posted. Looking at the first eight numbers, 0 is bad as it has to be. The other seven answers are 0, 1, 0, 2, 0, 1, 0. For the problem, they need to be 0, 1, 1, 2, 2, 2, 2. These do not appear, to me, to be the same numbers.
• 05-28-2009
quzah
I must be misunderstanding the original problem then.
Quote:

Every corresponding on bit indicates the channel is available. All I need to do is to find the first free channel based on the value in the byte.
0:00000000 - Broken, so check for zero first.
0:10000000 - First channel is available.
1:01000000 - Second channel is available.
0:11000000 - first...
2:00100000 - third...
0:10100000 - first...
1:01100000 - second...
0:11100000 - first...

That seems to fit for the quoted portion of the OP. Again, assuming we start with a returned zero being "first" channel, and count up from there. I'm not intentionally trying to be dense, I'm just tired, so it seems to fit the bill for what they're asking for. If it's not, someone point it out to me, because I'm just not seeing it.

Quzah.
• 05-28-2009
MK27
Quote:

Originally Posted by quzah
Again, assuming we start with a returned zero being "first" channel, and count up from there. I'm not intentionally trying to be dense,

I thought Snafuist's thing was for returning the number of trailing zero's, *not* the the first zero.
• 05-28-2009
quzah
Quote:

Originally Posted by MK27
I thought Snafuist's thing was for returning the number of trailing zero's, *not* the the first zero.

I just figured he worded it wrong, because the code he produced can be used effectively, if you look at what it's doing. Especially, since the assignment doesn't actually care about zeros, it cares about 1s.

That's why I said I think it's being misunderstood. It's not actually detecting zeros. It's detecting the first set bit, which is exactly what the OP was looking for, as best I can tell.

Quzah.
• 05-28-2009
tabstop
Quote:

Originally Posted by quzah
I must be misunderstanding the original problem then.

0:00000000 - Broken, so check for zero first.
0:10000000 - First channel is available.
1:01000000 - Second channel is available.
0:11000000 - first...
2:00100000 - third...
0:10100000 - first...
1:01100000 - second...
0:11100000 - first...

That seems to fit for the quoted portion of the OP. Again, assuming we start with a returned zero being "first" channel, and count up from there. I'm not intentionally trying to be dense, I'm just tired, so it seems to fit the bill for what they're asking for. If it's not, someone point it out to me, because I'm just not seeing it.

Quzah.

1 is actually 0000 0001, not 1000 0000, is I guess what you're missing, and therefore the eighth channel is the one that's available. So when you get to say 5, for 0000 0101, we need the sixth channel, but you are giving us the eighth.
• 05-28-2009
Snafuist
Quote:

Originally Posted by quzah
That's why I said I think it's being misunderstood. It's not actually detecting zeros. It's detecting the first set bit, which is exactly what the OP was looking for, as best I can tell.

It's detecting the least significant bit set, but the OP wants to detect the most significant bit set.

Greets,
Philip
• 05-28-2009
quzah
Quote:

Originally Posted by tabstop
1 is actually 0000 0001, not 1000 0000, is I guess what you're missing, and therefore the eighth channel is the one that's available. So when you get to say 5, for 0000 0101, we need the sixth channel, but you are giving us the eighth.

Reverse the order the bits are displayed. Look at my printing loop. Look again also at the first page, where someone says:

00000000
12345678

Quote:

It's detecting the least significant bit set, but the OP wants to detect the most significant bit set.
Ah, ok. I was going from that section I quoted earlier:
Quote:

Every corresponding on bit indicates the channel is available. All I need to do is to find the first free channel based on the value in the byte.
Which, the code seemed to fit the bill of. I wasn't seeing the portion where they flipped 180 degrees on what they said they wanted.

They don't really want the FIRST free channel, they want the LAST free channel. Silly OP, say what you mean and you'd have saved three pages of discussion. Anyway, reverse the order of how you check the bits in my first post, and you're fine. Or just use a LUT. ;)
[/edit]

Quzah.
• 05-28-2009
tabstop
Quote:

Originally Posted by quzah
Reverse the order the bits are displayed. Look at my printing loop. Look again also at the first page, where someone says:

00000000
12345678

Quzah.

I was aware of your printing loop being backwards. That's my point -- because you are printing the numbers backwards, you are therefore confusing "first" and "last".
• 05-28-2009
itCbitC
Obviously an endianness issue.
• 05-28-2009
quzah
Quote:

Originally Posted by tabstop
I was aware of your printing loop being backwards. That's my point -- because you are printing the numbers backwards, you are therefore confusing "first" and "last".

I wasn't, the OP was. They said they wanted the first, but they don't really mean first. When you count up from zero, the lowest numbers are "first". You can't say infinity is the first number, and then count down as "infinity -1" is the SECOND number. You say 1 is first, 2 is second... that's why they're called "one" and "two". ;)

The ordering didn't confuse me, the OP saying they wanted "first" when really they wanted "last" confused me. :D

Quzah.
• 05-28-2009
MK27
So: reverse the bits and perform these operations, which still includes a lookup table? If I were the OP I would have chewed part of my arm off by now ;)
• 05-28-2009
itCbitC
Here's my 2c:
Code:

```#include <stdio.h> #define UISZ sizeof(unsigned) * 8 int main(void) {     unsigned n, t, sz;     n = 1741823;     for (sz = UISZ - 1; sz; --sz)         if ((n & (t = (unsigned) 1 << sz)) == t)             return printf("free channel at bit %d\n", UISZ - sz);     printf("no free channels\n"); }```
• 05-28-2009
Snafuist
Now I have a very space efficient solution: the length of an unsigned binary number x is determined by L = ceil(log2(x)) + 1. Hence, CHAR_BITS - L is what the OP is looking for.

Somebody might want to check whether this is correct (ceil() or floor()? +1 or -1?).

Going to bed now,
Philip
• 05-28-2009
tabstop
Quote:

Originally Posted by quzah
I wasn't, the OP was. They said they wanted the first, but they don't really mean first. When you count up from zero, the lowest numbers are "first". You can't say infinity is the first number, and then count down as "infinity -1" is the SECOND number. You say 1 is first, 2 is second... that's why they're called "one" and "two". ;)

The ordering didn't confuse me, the OP saying they wanted "first" when really they wanted "last" confused me. :D

Quzah.

When referring to pieces of written material in languages such as English, "first" generally means the ones you come to first. The first letter of cat is c, and the first digit of 357 is 3. The fact that that is the digit that is worth the most is irrelevant.
• 05-28-2009
quzah
Quote:

Originally Posted by tabstop
The fact that that is the digit that is worth the most is irrelevant.

In a numbering system, the "first" digit is the lowest*. In a binary system, the lowest bit is considered the first. Why? Because you have to start somewhere and work up. You can't start at the high and work down. Why's that?

0001
0000 0001
0000 0000 0000 0001

All of those are 1 (assuming your version of how you order numbers, versus my displaying them "backwards"). The "first" digit in all of those is 1. That's the "first". That's how numbering in binary works. The "first" digit isn't the "most significant". Given a possible unknown quantity of bits, you take the "first" as the lowest, not the greatest. That'd just be wrong.

*excluding signed numbers, and the whole signed bit argument.

Quzah.
Show 80 post(s) from this thread on one page
Page 4 of 6 First 123456 Last