#c #bit-manipulation #bit
#c #манипулирование битами #бит
Вопрос:
Недавно я столкнулся с фрагментом кода, который предположительно работает нормально, но я не совсем понимаю, почему.
size_t a = 19;
std::cout<<std::bitset<8>(a)<<std::endl;
a ^= a amp; -a;
std::cout<<std::bitset<8>(a)<<std::endl;
Этот фрагмент кода инвертирует младший значащий бит заданного целого числа без знака. Я бы предпочел просто написать a ^= 1; , но я озадачен тем, почему приведенный выше фрагмент кода действительно работает. Я бы подумал, что unsigned int отрицательное значение приведет к неопределенному поведению?
Комментарии:
1. Осторожно: он переворачивает наименее значимый установленный бит (первый установленный бит снизу), а не младший значащий бит (который может быть 0 или 1). Этот код не эквивалентен
a ^= 1;(но он эквивалентенa amp;= a - 1;
Ответ №1:
a amp; -a дает вам наименьший значимый 1-битный набор в a . Для нечетного числа это действительно 1, но, конечно, в целом это не так.
Создание unsigned отрицательного значения является четко определенным и иногда полезным обозначением: -a для положительного a значения является -a 2N, где N — количество битов в типе. Альтернативой записи size_t a = std::numeric_limits<size_t>::max(); является, например, запись size_t a = -1; .
Таким образом, a ^= a amp; -a; переворачивает наименее значимый бит 1 в 0.
На самом деле довольно умно.
Комментарии:
1. Смотрите также [conv.integral]/p2
Ответ №2:
Как уже указывала @Bathsheba, этот трюк дает вам наименьший 1-битный набор в a. Однако я хотел бы более подробно рассказать, почему это происходит. Отрицание целого числа без знака в C эквивалентно отрицанию дополнения two:
Унарные арифметические операторы
[…]
Встроенный унарный оператор minus вычисляет отрицание своего продвинутого операнда. Для неподписанного a значение -a равно 2b -a, где b — количество бит после продвижения.
(см. cppreference / Арифметические операторы)
Для чисел дополнения two отрицание может быть выполнено следующим образом:
unsigned a = ...;
a = ~a;
a = 1;
Если бы не приращение, то у ~a не было бы общих битов с a , и результат был бы нулевым. Это относится к числу дополнений. Однако из-за приращения последний значимый набор 1-бит в a также становится установленным. Например:
16 = 0b0001'0000
~16 = 0b1110'1111 = -17
~16 1 = 0b1111'0000 = -16
-16 amp; 16 = 0b0001'0000 = 16
10 = 0b0000'1010
~10 = 0b1111'0101 = -11
~10 1 = 0b1111'0110 = -10
-10 amp; 10 = 0b0000'0010 = 2
a ^= a amp; -a затем переворачивает наименее значимый бит 1 в 0.
Что это математически делает, так это:
- округлите до следующего кратного степени двойки
- преобразуйте любую степень 2 в 0
- 0 остается неизменным
Также обратите внимание, что начиная с C 20, числа со знаком должны быть представлены с использованием дополнения two. Например, это означает, что переполнение целого числа со знаком больше не является неопределенным поведением.
Диапазон значений
[…]
До C 20 стандарт C допускал любое представление целых чисел со знаком, а минимальный гарантированный диапазон N-разрядных целых чисел со знаком составлял от — (2N-1-1) до 2N-1-1 (например, от -127 до 127 для 8-разрядного типа со знаком), что соответствует пределам дополнения или знака и величины.
Однако все компиляторы C используют представление с дополнением two, и начиная с C 20 это единственное представление, разрешенное стандартом, с гарантированным диапазоном от -2N-1 до 2N-1 -1 (например, от -128 до 127 для 8-разрядного типа со знаком).