Qualcuno potrebbe aiutare a spiegare cosa fa questo rivestimento C?

Question

Di solito riesco a capire la maggior parte del codice C ma questo è sopra la mia testa.

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

un esempio d'uso sarebbe qualcosa come:

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

Alcuni altri esempi sono:

1 a 1
2 a 2
7 a 8
31 a 32
da 60 a 64
da 3000 a 4096

So che sta arrotondando un numero intero alla sua potenza più vicina di 2, ma questo è il più possibile delle mie conoscenze.

Qualsiasi spiegazione sarebbe molto apprezzata.

Grazie

Answer 1

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

1. Diminuzione x da 1
2. OR x con (x/2).
3. O x con (x/4).
4. O x con (x/16).
5. O x con (x/256).
6. O x con (x/65536).
7. Aumentare x da 1.

Per un numero intero senza segno a 32 bit, questo dovrebbe spostare un valore massimo di potenza più vicina 2 che è uguale o maggiore. Le sezioni OR impostano tutti i bit più in basso sotto il bit più alto, quindi finisce con una potenza di 2 meno uno, quindi ne aggiungi uno indietro. Sembra che sia alquanto ottimizzato e quindi non molto leggibile; eseguendolo tramite operazioni bit a bit e spostamento di bit da solo e come macro (quindi nessuna chiamata di funzione in testa).

Answer 2

Le operazioni bit a bit o shift essenzialmente impostano ogni bit tra il bit e il bit zero più alto. Ciò produrrà un numero del modulo 2^n - 1. L'incremento finale aggiunge uno per ottenere un numero del modulo 2^n. Il decremento iniziale garantisce di non arrotondare i numeri che sono già poteri di due fino alla potenza successiva, in modo tale che ad es. 2048 non diventi 4096.

Answer 3

alla mia macchina kroundup32 dà 6.000m giri/sec
E la prossima funzione fornisce turni 7.693m/sec

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); 
    } 
} 

Così @thomasrutter profondo del cuore non dire che è "altamente ottimizzato".

e appropriato (solo una parte significativa) di montaggio (per 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 

Per qualche motivo non hanno trovato adeguata attuazione scan_msb (come #define scan_msb(x) if (__builtin_constant_p (x)) ...) entro le intestazioni standart di GCC (solo __TBB_machine_lg/__TBB_Log2).