Thread: Bits and bytes- Please help.

  1. #46
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by quzah View Post
    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.

  2. #47
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I must be misunderstanding the original problem then.
    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.
    Hope is the first step on the road to disappointment.

  3. #48
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by quzah View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #49
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by MK27 View Post
    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.
    Hope is the first step on the road to disappointment.

  5. #50
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by quzah View Post
    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.

  6. #51
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by quzah View Post
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  7. #52
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by tabstop View Post
    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

    [edit]
    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:
    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.
    Last edited by quzah; 05-28-2009 at 02:41 PM.
    Hope is the first step on the road to disappointment.

  8. #53
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by quzah View Post
    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".

  9. #54
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Obviously an endianness issue.

  10. #55
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by tabstop View Post
    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.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #56
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #57
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    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");
    }

  13. #58
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  14. #59
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by quzah View Post
    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.


    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.

  15. #60
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by quzah; 05-28-2009 at 03:14 PM. Reason: fixed crazy ass 13 bit number
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. SDLKey to ASCII without unicode support?
    By zacs7 in forum Game Programming
    Replies: 6
    Last Post: 10-07-2007, 03:03 AM
  3. trying to convert system bytes into bits and nibbles.
    By kraze_505 in forum C Programming
    Replies: 11
    Last Post: 01-25-2006, 02:27 AM
  4. Bits & Bytes
    By C of Green in forum C++ Programming
    Replies: 8
    Last Post: 06-21-2002, 06:50 PM
  5. Bits, Bytes & Nibbles!
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 10-13-2001, 10:22 PM