Как можно перебрать число по всем возможным значениям маски?

Question

Учитывая битовую маску, где установленные биты описывают, где другое число может быть одним или нулем, а неустановленные биты должны быть равны нулю в этом числе. Какой хороший способ перебрать все возможные значения?

Например:

000 returns [000]
001 returns [000, 001]
010 returns [000, 010]
011 returns [000, 001, 010, 011]
100 returns [000, 100]
101 returns [000, 001, 100, 101]
110 returns [000, 010, 100, 110]
111 returns [000, 001, 010, 011, 100, 101, 110, 111]

Самый простой способ сделать это - сделать это так:

void f (int m) {
    int i;
    for (i = 0; i <= m; i++) {
        if (i == i & m)
            printf("%d\n", i);
    }
}

Но это повторяет слишком много чисел. Должно быть порядка 32, а не 2 ** 32.

Answer 1

Для этого есть хитрый трюк (он подробно описан в книге Кнута «Искусство компьютерного программирования», том 4А, §7.1.3; см. Стр. 150):

С учетом маски maskи текущую комбинацию bits, вы можете сгенерировать следующую комбинацию с помощью

bits = (bits - mask) & mask

... начиная с 0 и продолжая до тех пор, пока не вернетесь к 0. (Используйте целочисленный тип без знака для переносимости; этоне будет работать должным образом с целыми числами со знаком на машинах, не являющихся дополнением к двум. Целое число без знака - лучший выбор для значения, которое в любом случае рассматривается как набор битов.)

Пример на C:

#include <stdio.h>

static void test(unsigned int mask)
{
    unsigned int bits = 0;

    printf("Testing %u:", mask);
    do {
        printf(" %u", bits);
        bits = (bits - mask) & mask;
    } while (bits != 0);
    printf("\n");
}

int main(void)
{
    unsigned int n;

    for (n = 0; n < 8; n++)
        test(n);
    return 0;
}

, что дает:

Testing 0: 0
Testing 1: 0 1
Testing 2: 0 2
Testing 3: 0 1 2 3
Testing 4: 0 4
Testing 5: 0 1 4 5
Testing 6: 0 2 4 6
Testing 7: 0 1 2 3 4 5 6 7

(... и я согласен, что ответ для 000 должен быть [000]!)

Answer 2

Прежде всего, непонятно, почему 000 не вернется [000]. Это ошибка?

В противном случае, учитывая значение маски «m» и число «n», которое соответствует критерию (n & ~ m) == 0, я бы предложил написать формулу для вычисления следующего более высокого числа. Одна из таких формул использует операторы «и», «или», «не» и «+» по одному разу.

Answer 3

Трюк от @Matthew потрясающий. Вот менее сложная, но, к сожалению, менее эффективная, рекурсивная версия в Python:

def f(mask):
    if mask == "0":
        return ['0']
    elif mask == '1':
        return ['0', '1']
    else:
        bits1 = f(mask[1:])
        bits2 = []
        for b in bits1:
            bits2.append('0' + b)
            if mask[0] == '1':
                bits2.append('1' + b)
        return bits2

print f("101")  ===> ['000', '100', '001', '101']

Answer 4

Попробуйте этот код:

def f (máscara):
    se máscara == "0":
        voltar ['0 ']
    elif máscara == '1 ':
        voltar ['0 ', '1']
    else:
        bits1 = f (máscara [1:])
        bits2 = []
        para b em bits1:
            bits2.append ('0 '+ b)
            se máscara [0] == '1 ':
                bits2.append ('1 '+ b)
        voltar bits2

print f ("101") ===> ['000 ', '100', '001 ', '101']

é interessante.

Answer 5

Вы можете сделать это грубой силой.;-) Пример Ruby:

require 'set'
set = Set.new
(0..n).each do |x|
  set << (x & n)
end

(где set - установленный тип данных, т. Е. Удаляет дубликаты.)