Thread: Bits and bytes- Please help.

  1. #1
    Registered User
    Join Date
    May 2008
    Location
    India
    Posts
    30

    Bits and bytes- Please help.

    Hi,
    First of all very sorry for coming up with such a vague title. I couldn't think any better title for this thread.
    I have been asked to use a byte for representing 8 different channels. 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.

    for eg:
    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.

    Could someone please help with this?
    Thanks!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I don't know whether taking a binary log is faster than looping/seven if-statements, but if you want a "formula"-type answer, then binary log is your answer. (Well, it's sort of your answer -- you'll have to truncate to an integer and then subtract from 8.)

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Use an array of 256 integers as a lookup table.
    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

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    If the value is 3 (0000 0011) doesn't that mean that the first free channel is the third? If the value was 7 (0000 0111) you wouldn't say that the first free channel is the 15th right? Since you've only got 8 channels free.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by hk_mp5kpdw View Post
    If the value is 3 (0000 0011) doesn't that mean that the first free channel is the third? If the value was 7 (0000 0111) you wouldn't say that the first free channel is the 15th right? Since you've only got 8 channels free.
    Count from the left:
    Code:
    Value     00000011
    Channel # 12345678

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by hk_mp5kpdw View Post
    If the value is 3 (0000 0011) doesn't that mean that the first free channel is the third? If the value was 7 (0000 0111) you wouldn't say that the first free channel is the 15th right? Since you've only got 8 channels free.
    I don't see how it would matter whether you want to count backward or forward. Counting one way, 3 would mean the 7th, counting the other the third, but only if you also reverse the meaning of the bit (otherwise it would be the first). You cannot possibly conclude "15".
    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. #7
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Check in descending order for every byte if all lower-order bits are on.

    Hint: 2^n - 1 will give you exactly n nonzero bits. Any other bit is zero.
    So 2^4 - 1 = 16 - 1 = 15 = 1111 = 4 one bits.
    Last edited by Brafil; 05-28-2009 at 10:48 AM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Brafil
    Like "if (value == 255) return 1; else if (value == 127) return 2;"?
    Unless you change it to compare ranges, that would be even worse than "looping around the bits". Effectively, it would be simulating a lookup table with an if-else chain (maybe substituting with a switch would level the playing field, but I am not sure about these kinds of micro-optimisations).
    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

  9. #9
    Registered User
    Join Date
    May 2008
    Location
    India
    Posts
    30
    Quote Originally Posted by Brafil View Post
    Like "if (value == 255) return 1; else if (value == 127) return 2;"?
    yeah something like that. if the value > 128, then 1
    128>value>64,return 2.

    But I cannot go with this. As 8 channel is just an initial value. It might get up to 32 channels. In that case writing If will not help.
    As said in the previous post, binary log should be of some help. I do not know what it does exactly. I will look have a look and let's see if that solves my problem.

    Thanks to all for the replies.

    Thank you!

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by chakra
    As 8 channel is just an initial value. It might get up to 32 channels.
    In such a case it is likely that a lookup table would not be feasible, unless you extrapolate by using a smaller lookup table several times.
    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

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Just to make sure the OP understands what a lookup table is, because that will be the fastest answer
    Code:
    int lookup_table[255] {0, 8, 7, 7, 6, 6 .... 1}
    There are a lot of duplicate values but that does not matter. "0" would be for when there are no channels.

    So, if the value is 3, you check the value of lookup_table[3] (which is 7, as you say it ought to be). In this system 4 (0000 0100) and 5 (0000 0101) both indicate the 6th is the first open channel just as 2 and 3 both mean the 7th.

    If you have 32 channels you need a 4 byte value, so you could use the same table byte by byte but do some arithmetic (eg, check the most significant byte first and add 24 to the result).
    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. #12
    Registered User
    Join Date
    May 2008
    Location
    India
    Posts
    30
    Quote Originally Posted by MK27 View Post
    Just to make sure the OP understands what a lookup table is, because that will be the fastest answer
    Code:
    int lookup_table[255] {0, 8, 7, 7, 6, 6 .... 1}
    There are a lot of duplicate values but that does not matter. "0" would be for when there are no channels.

    So, if the value is 3, you check the value of lookup_table[3] (which is 7, as you say it ought to be). In this system 4 (0000 0100) and 5 (0000 0101) both indicate the 6th is the first open channel just as 2 and 3 both mean the 7th.

    If you have 32 channels you need a 4 byte value, so you could use the same table byte by byte but do some arithmetic (eg, check the most significant byte first and add 24 to the result).
    Thanks for the explanation on the lookup table.
    for the 32 channels, as said I can go byte by byte starting from msb . I will proceed to the next byte, only if the current byte is 0.For every proceeding ,8 will be added to the result.

    Also I had the look in the binary log. it takes some 4 to 5 if's for a 32 bit . Thanks to tabstop. Even that is faster, but surely not as this lookup.

    Thanks to all once again.

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    It's not really clear that a lookup table will be faster. If the table is not in cache, it will takes hundreds of cycles to perform a check that could be done in only a few cycles using shift-and-test. Not to mention that once the table is brought into cache, it will displace whatever was already there.

    LUTs are most useful when they are accessed in a tight loop. The LUT comes into cache a single time, then access is fast. If that's the access pattern you'll be using, it might be worth it. But you really should profile it to find out for sure.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by brewbuck View Post
    It's not really clear that a lookup table will be faster. If the table is not in cache, it will takes hundreds of cycles to perform a check that could be done in only a few cycles using shift-and-test
    Are you saying if I have an array in memory and I want to check the value of array[75] the entire array must be filo'd thru the processor? That seems silly, but I guess that is the nature of the beast.
    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

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MK27 View Post
    Are you saying if I have an array in memory and I want to check the value of array[75] the entire array must be filo'd thru the processor? That seems silly, but I guess that is the nature of the beast.
    No... But the cache logic will certainly cause more than just that one byte to be brought into cache. The cache is organized into cache lines. Entire cache lines are filled and purged at once.

    The cache line which a given chunk of memory gets loaded into depends on its address. If the array is located at an "unfortunate" address, it might actually take up to two extra cache lines, if the whole array is cached.

    My point is that loading a LUT into cache might take an awful lot longer than you think. One fun thing that can happen is, if you are trying to access two different LUTs within the same inner loop, and these LUTs happen to map to the same cache line, they constantly displace each other from cache, and this can slow things down by hundreds of times.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

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