What does this condition test?

Came across this conditional in some uncommented Objective-C code:

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

Where w is开发者_运维技巧 a size_t greater than 1.

Update: Added the code contained by the conditional for context.

It tests whether more than one bit is set in w, i.e. whether it's not an exact power of two. See here.

It seems it's checking for powers of two. If w is a power of 2, the bit representation of w and w-1 have no bit in common set to 1. Example : 100 for 4 and 011 for 3. Thus the bitwise and (& in C) will give false for any w which is a power of two.

Overall, the code fragment replaces the value of w with the next power of two that is greater than or equal to w.

Test code:

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

Results:

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

Results from obvious modification (not shown):

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

It checks that w is not zero nor a power of 2. In other words, it checks that there are at least 2 bits set.

Update: Upon closer inspection, its seems there may be a bug in the body of the if. When w is an unsigned type and has at least two bits set, one of which is the high-order bit, the while will loop forever.