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.

Thanks! 2. 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. Use an array of 256 integers as a lookup table. 4. 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. 5. Originally Posted by hk_mp5kpdw 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. Originally Posted by hk_mp5kpdw 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". 7. 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. 8. 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). 9. Originally Posted by Brafil 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. 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. 11. Just to make sure the OP understands what a lookup table is, because that will be the fastest answer
Code:
`int lookup_table {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 (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). 12. Originally Posted by MK27 Just to make sure the OP understands what a lookup table is, because that will be the fastest answer
Code:
`int lookup_table {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 (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. 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. 14. Originally Posted by brewbuck 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 the entire array must be filo'd thru the processor? That seems silly, but I guess that is the nature of the beast. 15. Originally Posted by MK27 Are you saying if I have an array in memory and I want to check the value of array 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. Popular pages Recent additions 