Что проверяет это условие?

Question

наткнулся на это условие в некомментированном коде Objective-C:

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

Где w size_t больше 1.

Обновление: Добавлен код, содержащийся в условии для контекста.

Answer 1

Он проверяет, установлено ли более чем один бит в w, т. Е. Не является ли точная степень двух Смотри здесь .

Answer 2

Кажется, он проверяет наличие двух степеней. Если w является степенью 2, битовое представление w и w-1 не имеет общего бита, установленного в 1. Пример: 100 для 4 и 011 для 3. Таким образом, битовая and (& в C) даст false для любого w, который является степенью двойки.

Answer 3

В целом, фрагмент кода заменяет значение w следующей степенью двойки, которая больше или равна w.

Тестовый код:

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

Результаты:

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

Результаты очевидной модификации (не показаны):

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

Answer 4

Он проверяет, что w не равно нулю и не равно степени 2. Другими словами, он проверяет, что установлено как минимум 2 бита.

Обновление: при ближайшем рассмотрении кажется, что в теле if может быть ошибка. Когда w является типом без знака и имеет по крайней мере два установленных бита, один из которых является старшим битом, while будет зацикливаться вечно.