Приращение "маскированных" битов

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

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

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

Ответ 1

Просто заполните бит non mask с помощью тех, чтобы они распространяли перенос:

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

Ответ 2

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

x = -(x ^ mask) & mask;

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

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

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

Ответ 3

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

Начнем с

x = mask

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

x = (x - 1) & mask

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