Czy ktoś mógłby pomóc w wyjaśnieniu, co robi ten jeden liniowiec?

Question

Zazwyczaj mogę znaleźć większość kodu C, ale ten jest ponad moją głową.

#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) 

przykład użycia wyglądałby:

int x = 57; 
kroundup32(x); 
//x is now 64 

Kilka innych przykładów:

1 do 1
2 do 2
7 do 8
31 do 32
60 do 64
3000 do 4096

Wiem, że zaokrąglanie liczby całkowitej do najbliższej potęgi 2, ale to tyle, o ile moja wiedza idzie.

Wszelkie wyjaśnienia byłyby bardzo mile widziane.

Dzięki

Answer 1

(--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) 

1. Zmniejszenie X o 1
2. lub X z (x/2).
3. OR x z (x/4).
4. OR x z (x/16).
5. OR x z (x/256).
6. OR x z (x/65536).
7. Wzrost X o 1.

Do 32-bitowej liczby całkowitej bez znaku, powinno przenosić wartość do najbliższego potęgi 2, która jest równa lub większa. Sekcje OR ustawiają wszystkie dolne bity poniżej najwyższego bitu, więc kończy się to mocą 2 minus jeden, po czym dodajesz do niej ponownie. Wygląda na to, że jest nieco zoptymalizowany, a przez to mało czytelny; robi to przez operacje bitowe i samo przesuwanie bitów, i jako makro (więc nie narzut funkcji).

Answer 2

Operacja bitowa lub przesunięcie zasadniczo ustawia każdy bit pomiędzy najwyższym ustawionym bitem a bitem zero. Spowoduje to utworzenie liczby postaci 2^n - 1. Ostateczny przyrost dodaje jeden, aby uzyskać numer postaci 2^n. Początkowy ubytek zapewnia, że ​​nie zaokrąglasz liczb, które są już mocami dwóch do następnej mocy, więc np. 2048 nie stać 4096.

Answer 3

na moim komputerze kroundup32 daje rundy 6.000m/s
I następna funkcja daje rund 7.693m/s

inline int scan_msb(int x) 
{ 
#if defined(__i386__) || defined(__x86_64__) 
    int y; 
    __asm__("bsr %1, %0" 
      : "=r" (y) 
      : "r" (x) 
      : "flags"); /* ZF */ 
    return y; 
#else 
#error "Implement me for your platform" 
#endif 
} 

inline int roundup32(int x) 
{ 
    if (x == 0) return x; 
    else { 
     const int bit = scan_msb(x); 
     const int mask = ~((~0) << bit); 
     if (x & mask) return (1 << (bit+1)); 
     else return (1 << bit); 
    } 
} 

Więc @thomasrutter woudn't mogę powiedzieć, że jest to "wysoce zoptymalizowany".

i właściwe (sens tylko część) montaż (dla GCC 4.4.4):

kroundup32: 
    subl $1, %edi 
    movl %edi, %eax 
    sarl %eax 
    orl %edi, %eax 
    movl %eax, %edx 
    sarl $2, %edx 
    orl %eax, %edx 
    movl %edx, %eax 
    sarl $4, %eax 
    orl %edx, %eax 
    movl %eax, %edx 
    sarl $8, %edx 
    orl %eax, %edx 
    movl %edx, %eax 
    sarl $16, %eax 
    orl %edx, %eax 
    addl $1, %eax 
    ret 

roundup32: 
    testl %edi, %edi 
    movl %edi, %eax 
    je .L6 
    movl $-1, %edx 
    bsr %edi, %ecx 
    sall %cl, %edx 
    notl %edx 
    testl %edi, %edx 
    jne .L10 
    movl $1, %eax 
    sall %cl, %eax 
.L6: 
    rep 
    ret 
.L10: 
    addl $1, %ecx 
    movl $1, %eax 
    sall %cl, %eax 
    ret 

z jakiegoś powodu nie znalazłem odpowiedniego wdrożenia scan_msb (jak #define scan_msb(x) if (__builtin_constant_p (x)) ...) wewnątrz nagłówków standart GCC (tylko __TBB_machine_lg/__TBB_Log2).