Vraag Hoe vind je de positie van het enige-set-bit in een 64-bit waarde met behulp van bitmanipulatie efficiënt?


Zeg gewoon dat ik de waarde van het type heb uint64_t gezien als reeks van octetten (1 octet = 8-bit). De uint64_t waarde is bekend met slechts één bit instellen op een MSB-positie. Dus, de uint64_t waarde kan in een van de volgende binaire representaties zijn:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000  pos = 7
00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000  pos = 15
00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000  pos = 23
00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000  pos = 31
00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000  pos = 39
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000  pos = 47
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000  pos = 55
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000  pos = 63

Ik heb een snelle functie nodig die de bit instellen positie, maar retourneert 0 als er geen bit is ingesteld.

Als het mogelijk is, wil ik het zonder lussen noch vertakkingen.


37
2017-09-01 19:02


oorsprong


antwoorden:


Vermenigvuldig de waarde met een zorgvuldig ontworpen 64-bits constante en maskeer vervolgens de bovenste 4 bits. Voor elke CPU met snelle 64-bit vermenigvuldiging is dit waarschijnlijk zo optimaal als je kunt krijgen.

int field_set(uint64_t input) {
    uint64_t field = input * 0x20406080a0c0e1ULL;
    return (field >> 60) & 15;
}

// field_set(0x0000000000000000ULL) = 0
// field_set(0x0000000000000080ULL) = 1
// field_set(0x0000000000008000ULL) = 2
// field_set(0x0000000000800000ULL) = 3
// field_set(0x0000000080000000ULL) = 4
// field_set(0x0000008000000000ULL) = 5
// field_set(0x0000800000000000ULL) = 6
// field_set(0x0080000000000000ULL) = 7
// field_set(0x8000000000000000ULL) = 8

clang implementeert dit in drie x86_64-instructies, de frameopstelling en opschoning niet meegerekend:

_field_set:
    push   %rbp
    mov    %rsp,%rbp
    movabs $0x20406080a0c0e1,%rax
    imul   %rdi,%rax
    shr    $0x3c,%rax
    pop    %rbp
    retq

Merk op dat de resultaten voor elke andere invoer vrij willekeurig zijn. (Dus doe dat niet.)

Ik denk niet dat er een haalbare manier is om deze methode uit te breiden om waarden in het bereik 7..63 direct te retourneren (de structuur van de constante staat dit niet toe), maar u kunt de resultaten converteren naar dat bereik door het resultaat te vermenigvuldigen door 7.


Met betrekking tot hoe deze constante werd ontworpen: ik begon met de volgende opmerkingen:

  • Niet-ondertekende vermenigvuldiging is een snelle bewerking op de meeste CPU's en kan nuttige effecten hebben. We zouden het moeten gebruiken. :)
  • Als u iets vermenigvuldigt met nul, wordt nul weergegeven. Aangezien dit overeenkomt met het gewenste resultaat voor een invoer zonder bits, doen we het tot nu toe goed.
  • Alles vermenigvuldigen met 1ULL<<63 (d.w.z., uw "pos = 63" -waarde) kan alleen maar resulteren in dezelfde waarde, of nul. (Er kunnen geen lagere bits worden ingesteld en er zijn geen hogere bits om te wijzigen.) Daarom moeten we een manier vinden om deze waarde als het juiste resultaat te behandelen.
  • Een handige manier om deze waarde zijn eigen correcte resultaat te maken, is door hem met 60 bits rechts te verschuiven. Dit verschuift naar "8", wat een voldoende representatie is. We kunnen doorgaan met het coderen van de andere uitgangen als 1 t / m 7.
  • Het vermenigvuldigen van onze constante met elk van de andere bitvelden is equivalent aan het naar links verschuiven ervan met een aantal bits gelijk aan zijn "positie". De rechterschuiving met 60 bits zorgt ervoor dat alleen de 4 bits links van een gegeven positie in het resultaat verschijnen. Zodoende kunnen we alle gevallen creëren behalve één als volgt:

     uint64_t constant = (
          1ULL << (60 - 7)
        | 2ULL << (60 - 15)
        | 3ULL << (60 - 23)
        | 4ULL << (60 - 31)
        | 5ULL << (60 - 39)
        | 6ULL << (60 - 47)
        | 7ULL << (60 - 55)
     );
    

Tot dusverre is de constante 0x20406080a0c0e0ULL. Dit levert echter niet het juiste resultaat op pos=63; deze constante is even, dus het vermenigvuldigen ervan met die invoer geeft nul. We moeten het laagste bit instellen (d.w.z. constant |= 1ULL) om die zaak te laten werken, ons de uiteindelijke waarde van 0x20406080a0c0e1ULL.

Merk op dat de bovenstaande constructie kan worden gewijzigd om de resultaten anders te coderen. De uitvoer van 8 is gefixeerd zoals hierboven beschreven en alle andere uitvoer moet passen in 4 bits (d.w.z., 0 tot 15).


38
2017-09-01 20:59



Hier is een draagbare oplossing, die echter langzamer zal zijn dan oplossingen die profiteren van gespecialiseerde instructies zoals clz(tel voorloopnullen). Ik heb opmerkingen toegevoegd bij elke stap van het algoritme die uitlegt hoe het werkt.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
   return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
    uint64_t t, c;
    t = a - 1; // create mask
    c = t >> 63; // correction for zero inputs
    t = t + c; // apply zero correction if necessary
    t = t & 0x0101010101010101ULL; // mark each byte covered by mask
    t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte
    t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position
    t = t + c; // apply zero correction if necessary
    return (int)t;
}

int main (void)
{
    int i;
    uint64_t a;
    a = 0;
    printf ("a=%016llx   bit_pos=%2d   reference_pos=%2d\n", a, bit_pos(a), 0);
    for (i = 7; i < 64; i += 8) {
        a = (1ULL << i);
        printf ("a=%016llx   bit_pos=%2d   reference_pos=%2d\n", 
                a, bit_pos(a), i);
    }
    return EXIT_SUCCESS;
}

De uitvoer van deze code zou er als volgt uit moeten zien:

a=0000000000000000   bit_pos= 0   reference_pos= 0
a=0000000000000080   bit_pos= 7   reference_pos= 7
a=0000000000008000   bit_pos=15   reference_pos=15
a=0000000000800000   bit_pos=23   reference_pos=23
a=0000000080000000   bit_pos=31   reference_pos=31
a=0000008000000000   bit_pos=39   reference_pos=39
a=0000800000000000   bit_pos=47   reference_pos=47
a=0080000000000000   bit_pos=55   reference_pos=55
a=8000000000000000   bit_pos=63   reference_pos=63

Op een x86_64-platform vertaalt mijn compiler bit_pos() in deze machine code:

bit_pos PROC 
        lea       r8, QWORD PTR [-1+rcx]
        shr       r8, 63
        mov       r9, 0101010101010101H
        lea       rdx, QWORD PTR [-1+r8+rcx]
        and       rdx, r9
        imul      r9, rdx
        shr       r9, 53
        lea       rax, QWORD PTR [-1+r8+r9]
        ret

[Latere update]

De antwoord door duskwuff maakte me duidelijk dat mijn oorspronkelijke denken onnodig ingewikkeld was. In feite kan de gewenste functionaliteit volgens de methode van duskwuff veel bondiger worden uitgedrukt als volgt:

/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
   return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
    const uint64_t magic_multiplier = 
         (( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) |
          (39ULL << 24) | (47ULL << 16) | (55ULL <<  8) | (63ULL <<  0));
    return (int)(((a >> 7) * magic_multiplier) >> 56);
}

Elke redelijke compiler zal de magische vermenigvuldiger, die dat is, vooraf berekenen 0x070f171f272f373fULL. De code die wordt uitgezonden voor een x86_64-doel krimpt naar

bit_pos PROC 
        mov       rax, 070f171f272f373fH
        shr       rcx, 7
        imul      rax, rcx
        shr       rax, 56
        ret

18
2017-09-01 19:41



Als u POSIX kunt gebruiken, gebruik dan de ffs() functie van strings.h (niet string.h!). Het geeft de positie van de minst significante bitreeks (één geïndexeerd) of een nul als het argument nul is. Op de meeste implementaties, een oproep naar ffs() is inline en gecompileerd in de overeenkomstige machine-instructie, zoals bsf op x86. De glibc heeft ook ffsll() voor long long argumenten die nog meer geschikt zouden moeten zijn voor uw probleem, indien beschikbaar.


14
2017-09-01 19:14



De waarde mod 0x8C levert een unieke waarde voor elk van de cases.

Deze waarde mod 0x11 is nog steeds uniek.

De tweede waarde in de tabel is de resulterende mod 0x11.

128 9
32768   5
8388608 10
2147483648  0
549755813888    14
140737488355328 2
36028797018963968   4
9223372036854775808     15

Dus een eenvoudige opzoektabel is voldoende.

int find_bit(uint64_t bit){ 
  int lookup[] = { the seventeen values };
  return lookup[ (bit % 0x8C) % 0x11];
}

Geen vertakking, geen compilertricks.

Voor de volledigheid is de array dat

{ 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0}

9
2017-09-01 19:40



Als u een algoritme voor de taak wilt in plaats van een ingebouwde, zal dit het doen. Het levert het bitnummer van de meest significante 1 bit op, zelfs als er meer dan één bit is ingesteld. Het vernauwt de positie door iteratief het be- schouwde bitbereik in helften te verdelen, te testen of er bits in de bovenste helft zijn ingesteld, waarbij de helft als het nieuwe bitbereik wordt genomen, en anders de onderste helft als het nieuwe bitbereik te nemen .

#define TRY_WINDOW(bits, n, msb) do { \
    uint64_t t = n >> bits;           \
    if (t) {                          \
        msb += bits;                  \
        n = t;                        \
    }                                 \
} while (0)

int msb(uint64_t n) {
    int msb = 0;

    TRY_WINDOW(32, n, msb);
    TRY_WINDOW(16, n, msb);
    TRY_WINDOW( 8, n, msb);
    TRY_WINDOW( 4, n, msb);
    TRY_WINDOW( 2, n, msb);
    TRY_WINDOW( 1, n, msb);

    return msb;
}

7
2017-09-01 19:20



C ++ -tag is verwijderd, maar hier is een draagbaar C ++ -antwoord, want je kunt het compileren met C ++ en een gebruiken extern C interface:

Als je een macht van 2 hebt en je trekt er een af, dan krijg je een binair getal met het aantal ingestelde bits gelijk aan de positie

Een manier om het aantal ingestelde bits te tellen (binair 1s) is verpakt, vermoedelijk het meest efficiënt door elke implementatie van de stl, in std::bitset lid functie count

Merk op dat uw specificatie dat heeft 0 terug voor beide 0 of 1, dus ik heb toegevoegd as_specified_pos om aan deze vereiste te voldoen. Persoonlijk zou ik het gewoon laten de natuurlijke waarde van teruggeven 64 wanneer gepasseerd 0 om te kunnen differentiëren, en voor de snelheid.

De volgende code moet uiterst draagbaar zijn en hoogstwaarschijnlijk per platform door compilerleveranciers worden geoptimaliseerd:

#include <bitset>

uint64_t pos(uint64_t val)
{
   return std::bitset<64>(val-1).count();
}

uint64_t as_specified_pos(uint64_t val)
{
    return (val) ? pos(val) : 0;
}

Op Linux met g ++ krijg ik de volgende gedemonteerde code:

0000000000000000 <pos(unsigned long)>:
   0:   48 8d 47 ff             lea    -0x1(%rdi),%rax
   4:   f3 48 0f b8 c0          popcnt %rax,%rax
   9:   c3                      retq
   a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)

0000000000000010 <as_specified_pos(unsigned long)>:
  10:   31 c0                   xor    %eax,%eax
  12:   48 85 ff                test   %rdi,%rdi
  15:   74 09                   je     20 <as_specified_pos(unsigned long)+0x10>
  17:   48 8d 47 ff             lea    -0x1(%rdi),%rax
  1b:   f3 48 0f b8 c0          popcnt %rax,%rax
  20:   f3 c3                   repz retq

3
2017-09-09 20:22



Moderne hardware heeft hiervoor gespecialiseerde instructies (LZCNT, TZCNT op Intel-processors).

De meeste compilers hebben intrinsieke eigenschappen om ze eenvoudig te genereren. Zie het volgende wikipedia-pagina.


3
2017-09-10 21:19



00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000  pos = 7

..., maar retourneert 0 als er geen bit is ingesteld.

Dit zal hetzelfde terugkeren als het eerste bit of geen bit is ingesteld; op x86_64 is dat precies wat bsrq doet:

int bsrq_x86_64(uint64_t x){
  int ret;
  asm("bsrq %0, %1":"=r"(ret):"r"(x));
  return ret;
}

Echter; als het eerste bit is ingesteld, wordt ook 0 geretourneerd; hier is een methode die in constante tijd zal lopen (geen looping of vertakking) en -1 als er geen bits zijn ingesteld (om te onderscheiden van wanneer het eerste bit is ingesteld).

int find_bit(unsigned long long x){
  int ret=0,
  cmp = (x>(1LL<<31))<<5; //32 if true else 0
  ret += cmp;
  x  >>= cmp;
  cmp = (x>(1<<15))<<4; //16 if true else 0
  ret += cmp;
  x  >>= cmp;
  cmp = (x>(1<<7))<<3; //8
  ret += cmp;
  x  >>= cmp;
  cmp = (x>(1<<3))<<2; //4
  ret += cmp;
  x  >>= cmp;
  cmp = (x>(1<<1))<<1; //2
  ret += cmp;
  x  >>= cmp;
  cmp = (x>1);
  ret += cmp;
  x  >>= cmp;
  ret += x;
  return ret-1;
}

Technisch gezien geeft dit gewoon de positie van de meest significante set-bit terug. Afhankelijk van het type vlotter dat wordt gebruikt, kan dit in minder bewerkingen worden gedaan met behulp van het snel-inverse vierkant of een ander beetje twiddling hacks

Als je het niet erg vindt om de ingebouwde compilers te gebruiken, kun je gewoon:

__builtin_popcountll(n-1) of __builtin_ctzll(n) of __builtin_ffsll(n)-1


3
2017-09-10 22:56



Een eenvoudige opzoekoplossing. m=67 is het kleinste gehele getal waarvoor de waarden (1<<k)%m zijn allemaal verschillend, for k<m. Met (python transponeerbare code):

lut = [-1]*67
for i in range(0,64) : lut[(1<<i)%67] = i

Dan lut[a%67] geeft k als a = 1<<k. -1 waarden zijn niet gebruikt.


-1
2018-01-27 07:46