Thread: Bits and bytes- Please help.

  1. #16
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    int blah( unsigned char b )
    {
        return b&1?0:b&2?1:b&4?2:b&8?3:b&16?4:b&32?5:b&64?6:b&128?7:-1;
    }
    Assuming you don't want a look up table, as mentioned before, a series of if checks is as fast as you're going to get. However, I don't see the point of doing any math (dividing in a loop, etc), when you can just AND each bit. This assumes you want eight channels, numbered from zero to seven, with -1 for error.

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

  2. #17
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    I would imagine an enumeration of your channel listing 8 or up to 32, then logical AND the input to those values to get what you need.

  3. #18
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    For a 32-bit target operand the lookup table approach is pretty expensive in terms of storage and pushes the OS into doin' paging / swapping. IMO, one of the bit scan instructions is the way to go.

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by itCbitC
    For a 32-bit target operand the lookup table approach is pretty expensive in terms of storage
    That is why you would use a smaller lookup table, which is kind of a hybrid between checking each bit individually and having an entry in the lookup table for each possible input.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by chakra View Post
    if byte has the value 3 (0000 0011), I need to say 7th channel is free of usage.
    if the value is 255(1111 1111), then 1st channel is free for usage .

    I need to arrive at this decision ASAP, as this function is expected to be heavily used.
    Looping around the bits will not be a feasible solution.
    Do a bitwise negation of the value and use my Computing Trailing Zeros HOWTO for a constant time check.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  6. #21
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Snafuist View Post
    Do a bitwise negation of the value and use my Computing Trailing Zeros HOWTO for a constant time check.

    Greets,
    Philip
    That is certainly an interesting idea, but I'd kind of like to see how you think this will not be the slowest method?
    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

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Snafuist View Post
    Do a bitwise negation of the value and use my Computing Trailing Zeros HOWTO for a constant time check.

    Greets,
    Philip
    How would that answer the question?

  8. #23
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    mask byte0
        if byte
            do what was done above, sanz returning -1
    mask byte1
        if byte
            ...
    ...
        return -1
    Should end up with something like a maximum of four masks and a possible eleven IF checks, for a 32bit number. You could drop seven of those if you used a lookup table, so four masks and a possible four table checks.


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

  9. #24
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    How would that answer the question?
    For one byte, 8 - the number of trailing zeros (after inversion) will be the first free channel. However, considering the process involved, it might be like assembling a bicycle in order to cross the street.
    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

  10. #25
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by laserlight View Post
    That is why you would use a smaller lookup table, which is kind of a hybrid between checking each bit individually and having an entry in the lookup table for each possible input.
    If I get it, what happens if the value lies outside the index of values in the lookup table?

  11. #26
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by MK27 View Post
    That is certainly an interesting idea, but I'd kind of like to see how you think this will not be the slowest method?
    Computing the number of trailing zeros takes exactly 5 operations (independent of the size of the input number). Consider the following code (for computing the NTZ in 32 bits)

    Code:
    unsigned int v;  // 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];
    The 5 operations are:
    - bitwise AND
    - subtraction
    - multiplication
    - bitshift
    - array lookup

    Can you do it in less than 5 ops?

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  12. #27
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by itCbitC View Post
    If I get it, what happens if the value lies outside the index of values in the lookup table?
    How will a one byte value do that? Or, for the 32-bit value, what int?
    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

  13. #28
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Snafuist View Post
    Can you do it in less than 5 ops?

    Greets,
    Philip
    Yeah, I can do it in 1 with a lookup table.


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

  14. #29
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    For one byte, 8 - the number of trailing zeros (after inversion) will be the first free channel. However, considering the process involved, it might be like assembling a bicycle in order to cross the street.
    Except, of course, it won't. Consider the input 10101010....

  15. #30
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    Except, of course, it won't. Consider the input 10101010....
    Gosh tabstop, that is a pretty hard objection to object to.
    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

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