Значение (n & 1 ‹‹ b) в C++

Ссылаясь на код C++, написанный кем-то другим в CodeChef для конкретной проблемы, я нашел новый способ (по крайней мере, для меня) написания условного оператора, подобного этому: if (n & 1 << b). Весь фрагмент кода (функция) выглядит следующим образом:

int Solve(int tim, int n)
{
    if (tim < 0) 
         return 1;

    int res = 0;
    for (int b = Maxb - 1; b >= 0; b--)
        if (n & 1 << b) 
        {
            int my = b - __builtin_popcount(tim & ((1 << b) - 1));
            res += 1 << my;

            if (tim & 1 << b) 
                 return res;
        }

    res++;
    return res;
}

Я знаю побитовую операцию И, а также операцию сдвига влево, когда мы используем по отдельности. Однако здесь комбинация обоих в условном операторе заставила меня запутаться, чтобы прочитать логику. Когда я искал ссылки, я не мог найти ситуации, когда обе операции встречаются вместе. Поэтому может ли кто-нибудь сказать мне значение или что именно здесь происходит?


c++ c++14 bit-shift bitwise-operators
person Community    schedule 27.02.2018    source источник
comment
Приоритет оператора означает, что это n & (1 << b). Это помогает?   -  person Ry-♦    schedule 27.02.2018
comment
Сдвиг 1 влево на b мест дает тот же результат, что и возведение 2 в степень b.   -  person Omer Tuchfeld    schedule 27.02.2018
comment
если b равно 0, это будет false, так как оно вообще не будет зависеть от n. если b > 0, то это будет зависеть исключительно от n. это странная конструкция, но правдоподобная для хакеров ядра.   -  person Shark    schedule 27.02.2018
comment
@Ryan: это означает, что сначала выполняется сдвиг влево, а затем И вправо. Вот что я хотел бы уточнить.   -  person    schedule 27.02.2018
comment
Он сдвигает 1 влево на b позиций, а затем результат ставится на n. en.cppreference.com/w/cpp/language/operator_precedence   -  person Omer Tuchfeld    schedule 27.02.2018
comment
@ Омер: Хорошо. Теперь ясно. Спасибо всем за ответы.   -  person    schedule 27.02.2018

Ответы (2)


arrow_upward
7
arrow_downward

Это проверка того, включен или выключен бит в позиции 'b' в двоичном представлении n.

if (n & 1 << b)

по существу

if (n & (1 << b))

из-за приоритета оператора.

это значения, которые получает 1 ‹‹ b (правая часть в двоичном формате):

Для б == 0, (1 << b) == ...000000001

Для б == 1, (1 << b) == ...000000010

Для б == 2, (1 << b) == ...000000100

Для б == 3, (1 << b) == ...000000100

Для б == 3, (1 << b) == ...000001000

Для б == 4, (1 << b) == ...000010000

и так далее.

Когда вы & значение 1 << b с помощью n, вы по существу отключаете все биты n, кроме бита в ячейке, соответствующей 1 в двоичном представлении 1 << b.

Это означает, что вы получите ненулевой результат для n & (1 << b) только в том случае, если бит n, который находился в ячейке, соответствующей биту 1 (1 << b), был включен. Если бы это было не так, все биты отключились бы, и, поскольку он уже был 0, он остался бы 0, а конечный результат был бы 0.

Оператор if получает этот окончательный результат, если он положительный (бит был включен), он войдет в if, в противном случае (если бит был выключен) конечный результат будет равен 0, а оператор if будет рассматривать оператор n & (1 << b) как false. .

person Omer Tuchfeld    schedule 27.02.2018
comment
да... теперь все ясно. Большое спасибо, Омер за подробное объяснение. - person ; 27.02.2018

arrow_upward
0
arrow_downward

Согласно http://en.cppreference.com/w/cpp/language/operator_precedence

<< имеет приоритет над &. Итак, как и в комментарии @Ryan, (n & 1 << b) эквивалентно (n & (1 << b)).

person dub stylee    schedule 27.02.2018