• Forums
• Posts
Latest Posts
Active Posts
Recently Visited
Search Results
• Page Extras
• Forum Themes

### Hot!Fastest way to count bits in a byte?

Page: 123 > Showing page 1 of 3
Author
AndersG
Senior Member
• Total Posts : 156
• Reward points : 0
• Joined: 2008/08/05 04:51:24
• Location: 0
• Status: offline
0

# Fastest way to count bits in a byte?

I need to check that a byte is valid and the requirement is that the byte has to have at least 4 bits set. Is there a smart/fast way to do this or do I need to twiddle bits? :)

I do not need to know how many, just that they are >=4 so I can exit any loop after I found 4 bits.

Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:00:44 (permalink)
3 (1)
If they are in any order.
`int cnt=0;char c=0b00101011;for(int f=0;f<8;f++){    cnt+=c&1;    if(cnt==4)break; //if needed    c>>=1;}`

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
AndersG
Senior Member
• Total Posts : 156
• Reward points : 0
• Joined: 2008/08/05 04:51:24
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:05:09 (permalink)
0
Excactly. I guess there are no readymade hardware tricks for this :)
qhb
Superb Member
• Total Posts : 6260
• Reward points : 0
• Joined: 2016/06/05 14:55:32
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:07:44 (permalink)
4 (1)
Maybe just brute force for outright speed
`unsigned int counter=0;if (dat & 1)    counter++;if (dat & 2)    counter++;if (dat & 4)    counter++;if (dat & 8)    counter++;if (dat & 0x10)    counter++;if (dat & 0x20)    counter++;if (dat & 0x40)    counter++;if (dat & 0x80)    counter++;`

If the compiler is any good, each line could be one assembler instruction.
post edited by qhb - 2017/08/29 05:08:53
Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:07:52 (permalink)
0
Not if they are in random order otherwise it would be a straight mask.

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:19:29 (permalink)
0

mov.b#0b10101101,abyte

7 instructions
`clr cntclr bitchkdo #8-1,loopbtst abyte,bitchkbra z,\$+4inc cnt,cntloop: inc bitchk,bitchk`

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
qhb
Superb Member
• Total Posts : 6260
• Reward points : 0
• Joined: 2016/06/05 14:55:32
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:33:58 (permalink)
3 (1)
I'm not familiar with the dsPIC instruction set, but can you use a left shift and and "add with carry, zero" to do the summing. There would be no need for tests then.

simong123
Lab Member No. 003
• Total Posts : 1202
• Reward points : 0
• Joined: 2012/02/07 18:21:03
• Location: Future Gadget Lab (UK Branch)
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 05:36:46 (permalink)
4.67 (6)
Fastest:-
Lookup Table.

Also Kernighan's methid:-
`unsigned int v; // count the number of bits set in vunsigned int c; // c accumulates the total bits set in vfor (c = 0; v; c++){  v &= v - 1; // clear the least significant bit set}`

Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 06:08:38 (permalink)
2.5 (2)
The fastest

A lot quicker using carry and add.  Down to 4 instructions and if you want to count zeros, add this after "sl".
btg SR,#C

`clr cntdo #8-1,loopsl.b abyte,abyteloop: addc #0,cnt`

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
simong123
Lab Member No. 003
• Total Posts : 1202
• Reward points : 0
• Joined: 2012/02/07 18:21:03
• Location: Future Gadget Lab (UK Branch)
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 06:45:51 (permalink)
5 (2)
Gort2015:-
Your method may be the most compact of the counting methods (I don't know, I'm not familiar with Pic24 ASM), however how is it faster than a simple lookup into a static 256 byte array?
Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 08:23:08 (permalink)
1 (1)
Because he wants to count the bits in a single byte not an array.

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
simong123
Lab Member No. 003
• Total Posts : 1202
• Reward points : 0
• Joined: 2012/02/07 18:21:03
• Location: Future Gadget Lab (UK Branch)
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 08:28:41 (permalink)
5 (2)
Gort2015
Because he wants to count the bits in a single byte not an array.

Who said anything about counting the bits in an array?
`const uint8_t bitcount[256]={0,1,1,2,1,......}; unsigned CountBits(uint8_t byte){    return bitcount[byte];}`

post edited by simong123 - 2017/08/29 08:29:45
vjasinski
Super Member
• Total Posts : 109
• Reward points : 0
• Joined: 2013/04/30 11:48:06
• Location: Michigan, USA
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 08:31:22 (permalink)
4.67 (3)
Table is the fastest if you can afford the memory.

`uint8_t abyte;uint8_t numBits;static const unsigned uint8_t NumBitsTable[256] = { 0,1,1,2,1...7,8}numBits = NumBitsTable[abyte];`

1and0
Access is Denied
• Total Posts : 7670
• Reward points : 0
• Joined: 2007/05/06 12:03:20
• Location: Harry's Gray Matter
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 09:00:44 (permalink)
4.67 (3)
Lookup table is the FASTEST!  Take 2 or 4 cycles for BRA (dependent on PIC24/dsPIC3x devices) and 3 cycles for RETLW.

<edit> Above two posts show the C, here's the ASM:
`       bra     w0       ; ...Table: retlw   #0,w0       retlw   #1,w0       retlw   #1,w0       retlw   #2,w0       ; ...       retlw   #7,w0       retlw   #8,w0`

post edited by 1and0 - 2017/08/29 09:06:20
1and0
Access is Denied
• Total Posts : 7670
• Reward points : 0
• Joined: 2007/05/06 12:03:20
• Location: Harry's Gray Matter
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 09:07:03 (permalink)
4 (2)
That said, it takes only 4 cycles on an enhanced midrange devices PIC16F1. ;)

NorthGuy
Super Member
• Total Posts : 4800
• Reward points : 0
• Joined: 2014/02/23 14:23:23
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 09:09:46 (permalink)
5 (2)
And if you locate the table in RAM, then it's just one instruction/one cycle

`; LUT array address in w1; they byte in w0mov [w1+w0],w0; result in w0`

1and0
Access is Denied
• Total Posts : 7670
• Reward points : 0
• Joined: 2007/05/06 12:03:20
• Location: Harry's Gray Matter
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 09:12:56 (permalink)
4.5 (2)
NorthGuy
And if you locate the table in RAM, then it's just one instruction/one cycle
`; LUT array address in w1; they byte in w0mov [w1+w0],w0; result in w0`

grin:   True, I didn't even think about that.  Always have my LUTs in ROM.
1and0
Access is Denied
• Total Posts : 7670
• Reward points : 0
• Joined: 2007/05/06 12:03:20
• Location: Harry's Gray Matter
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 09:35:10 (permalink)
4.5 (2)
vjasinski
`static const unsigned uint8_t NumBitsTable[256] =     { 0,1,1,2,1...7,8}`

Here's one way to generate the LUT:
`static const uint8_t NumBitsTable[256] = {#define B2(n) n, n+1, n+1, n+2#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)    B6(0), B6(1), B6(1), B6(2)};`

Similar code can be done in ASM too.
post edited by 1and0 - 2017/08/29 09:36:18
Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 10:24:05 (permalink)
0
1and0
Lookup table is the FASTEST!  Take 2 or 4 cycles for BRA (dependent on PIC24/dsPIC3x devices) and 3 cycles for RETLW.

<edit> Above two posts show the C, here's the ASM:
`       bra     w0        ; ...Table: retlw   #0,w0       retlw   #1,w0       retlw   #1,w0       retlw   #2,w0       ; ...       retlw   #7,w0       retlw   #8,w0 `

That table would need 256 combinations since the 4 bits could be anywhere in the byte or it could even be empty, plus you need to mask w0 because it is a byte.

Say the bits were at: 0b1100101

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
+ ST:Continues, "What Ships are Made for", Q's back.
Gort2015
• Total Posts : 2083
• Reward points : 0
• Joined: 2015/04/30 10:49:57
• Location: 0
• Status: offline
Re: Fastest way to count bits in a byte? 2017/08/29 10:32:21 (permalink)
0
NorthGuy
And if you locate the table in RAM, then it's just one instruction/one cycle
`; LUT array address in w1 ; they byte in w0 mov [w1+w0],w0 ; result in w0`

Why would you want a table containing bytes 0 - 255 plus you are word indexing, it would cause an exception/address trap.

post edited by Gort2015 - 2017/08/29 10:34:49

MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.