При заданных n
и m
неподписанных интегральных типах выражение
(n & m) <= m
всегда верно?
При заданных n
и m
неподписанных интегральных типах выражение
(n & m) <= m
всегда верно?
Да, это правда.
Нетрудно заметить, что необходимым условием для y > x
является то, что по крайней мере одно битовое положение установлено на 1
в y
, но 0
в x
. Поскольку &
не может установить бит в 1
, если соответствующие биты операндов уже не были 1
, результат не может быть больше, чем операнды.
Да, это всегда верно для неподписанных целых типов данных.
В зависимости от значения маски n
некоторые 1 бит в m
могут стать 0-битами; все биты, которые равны 0 в m
, останутся 0
в результате. С точки зрения поддержания m
как можно выше, самое лучшее, что может случиться, это то, что все 1 биты останутся на месте, и в этом случае результат будет равен m
. Во всех остальных случаях результат будет меньше m
.
Пусть m
m 1 m 2 m 3 m 4 m 5 m 6 m 7 m 8, где m i немного.
Теперь пусть n
будет n 1 n 2 n 3 n 4 n < суб > 5суб > п <суб > 6суб > п <суб > 7суб > п <суб > 8суб > .
Что будет m & n
? Все биты в m
, которые изначально были равны 0, останутся 0, потому что 0 & anything
равно 0. Все биты, которые были 1, будут только 1 из соответствующего бита в n
равным 1.
Считая, что в "лучшем" случае число будет одинаковым, но никогда не может увеличиться, поскольку из 0 & anything
не может быть создано 1-е.
Давайте иметь пример, чтобы иметь лучшую интуицию:
Пусть m
будет 11101011.
Каковы числа, превышающие m
? 11111111 (тривиальный), 11111011, 11101111, 11111010, 11111110.
п <суб > 1суб > п <суб > 2суб > п <суб > 3суб > п <суб > 4суб > п <суб > 5суб > п < суб > 6суб > п <суб > 7суб > п <суб > 8суб >
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ &
1 1 0 1 0 1 1
-----------------------
Ни в коем случае вы не можете использовать любую из вышеперечисленных комбинаций.
Да. В дополнение к причинам, описанным в других ответах, несколько двоичных примеров делают довольно очевидным, что невозможно сделать результат большим, чем любой из аргументов:
0
1
------
0
1
1
------
1
111011
11111
------
11011
111011
111011
------
111011
Учитывая два аргумента, самое высокое, что мы можем достичь, - это то, что оба аргумента имеют одно и то же значение, результат равен значению двух аргументов (последний пример выше).
Невозможно сделать результат больше, независимо от того, к чему мы установили аргументы. Если вы в состоянии, то у нас серьезные проблемы.;)
n & m
имеет все биты, которые установлены в m
и в n
.
~n & m
имеет все биты, которые установлены в m
, но не в n
.
Добавление обеих величин даст все биты, которые установлены в m
. То есть m
:
m = (n & m) + (~n & m)
m ≥ (n & m)