Теория чисел: требуется решение

Question

Предположим, что a = a31 a30 . . . a1 a0 - это 32-битное двоичное слово.
Рассмотрим 32-разрядное двоичное слово b = b31 b30 . . . b1 b0 вычисленного по следующему алгоритму:

1. отсканировать справа налево и не копировать его биты в b до первого 1 найден (который также копируется в b)
2. После этого скопируйте булевские отрицания бит в a.

Например, a = 10100 . . . 00 преобразуется в b = 01100 . . . 00. Объясните, что вычисляет этот алгоритм, если a и b интерпретируются как двоичные числа.

Answer 1

Это для расчета комплемента 2.

Вы могли видеть, что b действительно равен ~a+1, что означает b является a «s 2 дополнения.

Answer 2

Это дополнение к двум, как отметил Тираму. Ответ легко найти, если вы уже знаете его (как и я), но сложнее получить.

Начнет с той частью, которая копируется:

copy_mask = a^(a - 1) // extract rightmost 1 and smear to the right 

Очевидно, что та часть, которая не копируется (и, таким образом, «отрицается», как вы назвали его) просто дополнение этой маски:

negated_mask = ~copy_mask 

И теперь мы можем построить b:

b = (a & copy_mask) | (~a & ~copy_mask) 

Замены:

b = (a & (a^(a - 1))) | (~a & ~(a^(a - 1))) 

Simplify:

// move complement into xor 
b = (a & (a^(a - 1))) | (~a & (a^~(a - 1))) 
// use two's complement definition 
b = (a & (a^(a - 1))) | (~a & (a^-a)) 
// use two's complement definition 
b = (a & ~(a^-a)) | (~a & (a^-a)) 
// use definition of xor: p^q = (p&~q)|(~p&q) 
b = a^(a^-a) 
// use xor associativity 
b = (a^a)^-a 
// simplify xor with self 
b = -a 

Там, наверное, более короткий путь, который не пропускает слишком много шагов ..