Cosa prova questa condizione?

Question

sono imbattuto in questo condizionale in qualche codice commentata Objective-C:

if (w & (w - 1)) 
{ 
    i = 1; 
    while (i < w) 
    { 
     i *= 2; 
    } 
    w = i; 
} 

Dove w è un size_t maggiore di 1.

Aggiornamento: Aggiunto il codice contenuto dal condizionale per il contesto.

Answer 1

Verifica se più di un bit è impostato in w, vale a dire se non è una potenza esatta di due. Vedi here.

Answer 2

Sembra che stia controllando i poteri di due. Se w è una potenza di 2, la rappresentazione dei bit w e w-1 avere nessun bit in serie comune a 1. Esempio: 100 per 4 e per 011 3. Così il bit and (& in C) darà false per qualsiasi w cui è un potere di due.

Answer 3

Controlla che w non sia zero né una potenza di 2. In altre parole, controlla che ci siano almeno 2 bit impostati.

Aggiornamento: a un'ispezione più ravvicinata, sembra che potrebbe esserci un bug nel corpo di if. Quando w è un tipo senza segno e ha almeno due bit impostati, uno dei quali è il bit di ordine più elevato, il ciclo while verrà interrotto per sempre.

Answer 4

Nel complesso, il frammento di codice sostituisce il valore di w con la potenza successiva di due che è maggiore o uguale a w.

codice di prova:

#include <stdio.h> 
size_t doit(size_t w) 
{ 
    if (w & (w - 1)) 
    { 
     size_t i = 1; 
     while (i < w) 
     { 
      i *= 2; 
     } 
     w = i; 
    } 
    return w; 
} 

int main(void) 
{ 
    size_t i; 
    for (i = 0; i < 1111111; i = (2*i+1)) 
    { 
     size_t x = doit(i); 
     printf("0x%06zX --> 0x%06zX\n", i, x); 
    } 
    for (i = 0; i < 1111111; i = (3*i+13)) 
    { 
     size_t x = doit(i); 
     printf("0x%06zX --> 0x%06zX\n", i, x); 
    } 
    return(0); 
} 

Risultati:

0x000000 --> 0x000000 
0x000001 --> 0x000001 
0x000003 --> 0x000004 
0x000007 --> 0x000008 
0x00000F --> 0x000010 
0x00001F --> 0x000020 
0x00003F --> 0x000040 
0x00007F --> 0x000080 
0x0000FF --> 0x000100 
0x0001FF --> 0x000200 
0x0003FF --> 0x000400 
0x0007FF --> 0x000800 
0x000FFF --> 0x001000 
0x001FFF --> 0x002000 
0x003FFF --> 0x004000 
0x007FFF --> 0x008000 
0x00FFFF --> 0x010000 
0x01FFFF --> 0x020000 
0x03FFFF --> 0x040000 
0x07FFFF --> 0x080000 
0x0FFFFF --> 0x100000 
0x000000 --> 0x000000 
0x00000D --> 0x000010 
0x000034 --> 0x000040 
0x0000A9 --> 0x000100 
0x000208 --> 0x000400 
0x000625 --> 0x000800 
0x00127C --> 0x002000 
0x003781 --> 0x004000 
0x00A690 --> 0x010000 
0x01F3BD --> 0x020000 
0x05DB44 --> 0x080000 

risultati di evidente modifica (non mostrate):

0x000001 --> 0x000001 
0x000002 --> 0x000002 
0x000004 --> 0x000004 
0x000008 --> 0x000008 
0x000010 --> 0x000010 
0x000020 --> 0x000020 
0x000040 --> 0x000040 
0x000080 --> 0x000080 
0x000100 --> 0x000100 
0x000200 --> 0x000200 
0x000400 --> 0x000400 
0x000800 --> 0x000800 
0x001000 --> 0x001000 
0x002000 --> 0x002000 
0x004000 --> 0x004000 
0x008000 --> 0x008000 
0x010000 --> 0x010000 
0x020000 --> 0x020000 
0x040000 --> 0x040000 
0x080000 --> 0x080000 
0x100000 --> 0x100000