Hot!Fastest way to count bits in a byte?

Page: 12 > Showing page 1 of 2
Author
AndersG
Senior Member
  • Total Posts : 135
  • Reward points : 0
  • Joined: 2008/08/05 04:51:24
  • Location: 0
  • Status: offline
2017/08/29 04:34:31 (permalink)
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.
#1

37 Replies Related Threads

    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #2
    AndersG
    Senior Member
    • Total Posts : 135
    • 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 :)
    #3
    qhb
    Superb Member
    • Total Posts : 5508
    • Reward points : 0
    • Joined: 2016/06/05 14:55:32
    • Location: One step ahead...
    • 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
    #4
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #5
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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 cnt
    clr bitchk
    do #8-1,loop
    btst abyte,bitchk
    bra z,$+4
    inc cnt,cnt
    loop: inc bitchk,bitchk

     

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #6
    qhb
    Superb Member
    • Total Posts : 5508
    • Reward points : 0
    • Joined: 2016/06/05 14:55:32
    • Location: One step ahead...
    • 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.
     
    #7
    simong123
    Lab Member No. 003
    • Total Posts : 1081
    • 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.6 (5)
    Fastest:-
    Lookup Table.
     
    Also Kernighan's methid:-

    unsigned int v; // count the number of bits set in v
    unsigned int c; // c accumulates the total bits set in v
    for (c = 0; v; c++)
    {
      v &= v - 1; // clear the least significant bit set
    }

    #8
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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 cnt
    do #8-1,loop
    sl.b abyte,abyte
    loop: addc #0,cnt


    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #9
    simong123
    Lab Member No. 003
    • Total Posts : 1081
    • 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?
    #10
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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.
     
    Read post #1.

    MPLab X playing up, bug in your code? Nevermind, Star Trek:Discovery will be with us soon.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #11
    simong123
    Lab Member No. 003
    • Total Posts : 1081
    • 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.
     
    Read post #1.

    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
    #12
    vjasinski
    Super Member
    • Total Posts : 92
    • 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];

    #13
    1and0
    Access is Denied
    • Total Posts : 6849
    • 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
    #14
    1and0
    Access is Denied
    • Total Posts : 6849
    • 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. ;)
     
    #15
    NorthGuy
    Super Member
    • Total Posts : 4396
    • Reward points : 0
    • Joined: 2014/02/23 14:23:23
    • Location: Northern Canada
    • 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 w0
    mov [w1+w0],w0
    ; result in w0

    #16
    1and0
    Access is Denied
    • Total Posts : 6849
    • 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 w0
    mov [w1+w0],w0
    ; result in w0


    grin: grin  True, I didn't even think about that.  Always have my LUTs in ROM.
    #17
    1and0
    Access is Denied
    • Total Posts : 6849
    • 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
    #18
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #19
    Gort2015
    Klaatu Barada Nikto
    • Total Posts : 1214
    • 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.
    https://www.youtube.com/watch?v=Iu1qa8N2ID0
    + ST:Continues, "What Ships are Made for", Q's back.
    #20
    Page: 12 > Showing page 1 of 2
    Jump to:
    © 2017 APG vNext Commercial Version 4.5