Bits and bytes- Please help.

This is a discussion on Bits and bytes- Please help. within the C Programming forums, part of the General Programming Boards category; Snafuist, please explain exactly how negating the input and then computing the number of trailing zeroes would give the answer. ...

  1. #31
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,662
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #32
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #33
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,662
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #34
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by quzah View Post
    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[8] = {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
    Last edited by Snafuist; 05-28-2009 at 01:28 PM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #35
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iMalc View Post
    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.
    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

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

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

  8. #38
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,662
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

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

  10. #40
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by quzah View Post
    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[32] = 
        {
            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. #41
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by quzah View Post
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

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

  13. #43
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by quzah View Post
    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. #44
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,662
    I think we can stop discussing Snafuist's suggestion now as Snafuist has admitted that it is based on an unwarranted assumption.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #45
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by laserlight View Post
    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[32] = 
        {
            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.
    Last edited by quzah; 05-28-2009 at 02:04 PM. Reason: ugly extra spaces
    Hope is the first step on the road to disappointment.

Page 3 of 6 FirstFirst 123456 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 12: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, 01: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21