Ответы на программистские задачи
На эти:
1. Как нетрудно видеть, значение mask & (mask-1) равно mask без младшей единицы. Тогда mask & ~(mask-1), или, более компактно, mask & -mask - собственно эта младшая единица, а (data & mask & -mask) != 0 - искомое выражение, с точностью до мелких деталей.
2. Вот мой вариант (в комментариях к задачам - альтернативные от
avva и spoon_gin):
Рассмотрим выражение A = ~mask | (data & mask). В нем единице равны все биты, кроме тех, которые в mask есть, а в data - нет. Что будет, если мы прибавим к этому выражению B = (data & mask)? Если в A есть хотя бы один ноль левее (старше) самого старшего бита в B, то переполнения при сложении не произойдет, а если нет - т.е. если самому старшему биту mask соответствовала единица в data - то произойдет.
Наличие переполнения определим сравнением суммы с любым из слагаемых: если сумма меньше, то оно было.
Итого: (~mask | (data & mask)) + (data & mask) < (data & mask)
1. Как нетрудно видеть, значение mask & (mask-1) равно mask без младшей единицы. Тогда mask & ~(mask-1), или, более компактно, mask & -mask - собственно эта младшая единица, а (data & mask & -mask) != 0 - искомое выражение, с точностью до мелких деталей.
2. Вот мой вариант (в комментариях к задачам - альтернативные от
avva и spoon_gin):Рассмотрим выражение A = ~mask | (data & mask). В нем единице равны все биты, кроме тех, которые в mask есть, а в data - нет. Что будет, если мы прибавим к этому выражению B = (data & mask)? Если в A есть хотя бы один ноль левее (старше) самого старшего бита в B, то переполнения при сложении не произойдет, а если нет - т.е. если самому старшему биту mask соответствовала единица в data - то произойдет.
Наличие переполнения определим сравнением суммы с любым из слагаемых: если сумма меньше, то оно было.
Итого: (~mask | (data & mask)) + (data & mask) < (data & mask)