Увеличение "маскированных" наборов битов

в настоящее время я пишу перечислитель дерева, где я столкнулся со следующей проблемой:

Я смотрю на маскированные битовые наборы, т. е. битовые наборы, где установленные биты являются подмножеством маски, т. е. 0000101 с маской 1010101. То, что я хочу сделать, - это увеличить битовый набор, но только по отношению к маскированным битам. В этом примере результатом будет 0010000. Чтобы сделать его немного яснее, извлеките только замаскированные биты, т. е. 0011, увеличьте их до 0100 и распределите их на биты маски снова, давая 0010000.

кто-нибудь видит эффективный способ сделать это, за исключением реализации операции вручную с использованием комбинации битов и префиксных масок?

3 78
javascript c++ bit-manipulation intrinsics

3 ответа:

просто заполните не маски битов с теми, так что они распространяются нести:

// increments x on bits belonging to mask
x = ((x | ~mask) + 1) & mask;
120

хотя это и не интуитивно понятно по сравнению с принятым ответом, это работает всего за 3 шага:

x = -(x ^ mask) & mask;

Это можно проверить, как предложил zch:

  -(x ^ mask)
= ~(x ^ mask) + 1  // assuming 2's complement
= (x ^ ~mask) + 1
= (x | ~mask) + 1  // since x and ~mask have disjoint set bits

тогда это становится эквивалентным принятому ответу.

19

если порядок итерации не так важен, и операция декремента удовлетворит ваши потребности, можно использовать только две операции:

С

x = mask

и получить Предыдущее значение

x = (x - 1) & mask

x - 1 часть изменений последнего ненулевого бита на ноль, а все менее значимые биты с 1 по. Затем & mask часть оставляет только биты маски среди них.

7