¿Qué prueba esta condición?

Question

encontré con esta condición en algún código de Objective-C sin comentar:

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

Dónde w es una size_t mayor que 1.

Actualización: Agregó el código contenido por el condicional para el contexto.

Answer 1

Comprueba si hay más de un bit configurado en w, es decir, si no tiene una potencia exacta de dos. Ver here.

Answer 2

Parece que está buscando poderes de dos. Si w es una potencia de 2, la representación de bits de w y w-1 no tienen ningún bit en conjunto común a 1. Ejemplo: 100 para 4 y 011 para 3. Así, el bit a bit and (& en C) dará falsa para cualquier w que es un poder de dos.

Answer 3

Comprueba que w no es cero ni tiene una potencia de 2. En otras palabras, comprueba que hay al menos 2 bits configurados.

Actualización: Tras una inspección más cercana, parece que puede haber un error en el cuerpo del if. Cuando w es un tipo sin firmar y tiene al menos dos bits establecidos, uno de los cuales es el bit de orden superior, el while se repetirá para siempre.

Answer 4

En general, el fragmento de código reemplaza el valor de w con la siguiente potencia de dos que es mayor o igual a w.

código de prueba:

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

Resultados:

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 

Resultados de la modificación obvia (no se muestra):

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