Следующие две функции C эквивалентны:Эквивалентность двух битовых операций
unsigned f(unsigned A, unsigned B) {
return (A | B) & -(A | B);
}
unsigned g(unsigned A, unsigned B) {
unsigned C = (A - 1) & (B - 1);
return (C + 1) & ~C;
}
Мой вопрос: почему они эквивалентны? Какие правила/преобразования происходят с g, которые преобразуют его в f?
1a. Выражение x & -x - это хорошо известный «бит-хак»: он оценивает значение, которое имеет все биты, установленные на 0, за исключением одного бита: младший бит 1 в исходном значении x. (Если x не 0, конечно.)
Например, в беззнаковой арифметике: 5 & -5 = 1, 4 & -4 = 4 т.д.
2a. Это немедленно сообщает нам, что делает функция f: используя оператор |, он объединяет все 1 бит в A и B, а затем находит самое низкое 1 в комбинированном значении. Другими словами, результат f - это слово, которое содержит подошву 1 бит в позиции самого низкого 1 в A или B.
1b. Выражение (x + 1) & ~x - это известный «бит взлома»: он оценивает все биты, установленные на 0, за исключением младшего разряда 0 в исходном значении x. Самый низкий 0 бит в x становится единственным 1 в результирующем значении. (Если это не x все-1-биты, конечно.)
Например, в беззнаковой арифметике: (5 + 1) & -5 = 2, (4 + 1) & -4 = 1 т.д.
2b. Выражение x - 1 заменяет все конечные 0 бит в x с 1 и заменяет самую низкую 1 в x с 0, сохраняя остальную часть x без изменений. Оператор & объединяет все бит 0 (точно так же, как оператор | объединяет все 1 бит). Это означает, что у (A - 1) & (B - 1) будет самый низкий 0 бит, где самый низкий 1 бит был в A или B.
3b. Per 1b, (C + 1) & ~C замещает, что самое низкое 0 с одиноким 1, обнуление всего остального.
Это означает, что g делает то же, что и f. Обе функции находят и возвращают самый низкий бит 1 между двумя входными значениями. Результат всегда равен 2 (или просто 0). Например. если хотя бы одно входное значение нечетно, результат равен 1.
У меня есть интуитивное чувство (которое может быть неправильно), что для того, чтобы построить формальное преобразование одной функции в другую путем применения дополнительных операций к существующим выражениям, необходимо, по крайней мере один из этих функций быть «обратимым» (это некоторое полуформальное значение термина). Ни один из этих двух не выглядит достаточно «обратимым» для меня ...
+1: никаких преобразований, но все еще отлично – perreal
@chux: Хорошая точка. Первоначально я предполагал, что бит-образ, созданный в неподписанном значении унарным '-', зависит от представления. Но это не так. – AnT
Незначительный: «... содержит единственную 1 бит в позиции самого низкого 1 в обоих А и В.» -> «самый низкий 1 в A или B.». «И», используемые здесь в английском смысле, несколько противоречат «A | B'. Хммм - Даже мое предложение выглядит неловко. – chux
Если две логические функции имеют одну и ту же таблицу истинности (что делает их эквивалентными), это не означает, что существуют правила, преобразующие одну функцию в другую. Более того, они могут использовать другую алгебру (набор операторов). –
Отметим также, что это не побитовые функции, так как они содержат арифметические операторы. –
Я не думаю, что они эквивалентны, предположим, что A равно 5, а B - 4, из fn f вернет 0, если fn g вернет ненулевое значение. – Bas