Подсчет, обратный битовый паттерн

Question

Я пытаюсь найти алгоритм для подсчета от 0 до 2 ⁿ -1, но их битовая комбинация поменялась местами. Я забочусь только о LSB слова. Как вы уже догадались, я потерпел неудачу.

Для n = 3:

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

Вы поняли идею.

Отлично, ответы в псевдокоде. Фрагменты кода на любом языке приветствуются, предпочтительны ответы без битовых операций.

Пожалуйста, не размещайте фрагмент без краткого объяснения или указателя на источник.

Edit: я забыл добавить, у меня уже есть наивная реализация, которая просто инвертирует переменную count. В некотором смысле этот метод на самом деле не считается.

Answer 1

Это, я думаю, проще всего с битовыми операциями, даже если вы сказали, что это не было предпочтительным

Предполагая 32-битные числа, вот изящный кусок кода, который может обратить все битов, не делая это в 32 шага:

 unsigned int i;
 i = (i & 0x55555555) <<  1 | (i & 0xaaaaaaaa) >>  1;
 i = (i & 0x33333333) <<  2 | (i & 0xcccccccc) >>  2;
 i = (i & 0x0f0f0f0f) <<  4 | (i & 0xf0f0f0f0) >>  4;
 i = (i & 0x00ff00ff) <<  8 | (i & 0xff00ff00) >>  8;
 i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
 i >>= (32 - n);

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

Последняя строка необходима для выравнивания битов так, чтобы bin "n" был старшим значащим битом.

Более короткие версии этого возможны, если «n» равно <= 16 или <= 8 </p>

Answer 2

На каждом шаге найдите крайнюю левую цифру 0 вашего значения. Установите его и очистите все цифры слева от него. Если вы не нашли цифру 0, значит, вы переполнились: верните 0, или остановите, или вылетите, или все, что вы хотите.

Это то, что происходит при обычном двоичном приращении (под этим я подразумеваю эффект, а не то, как он реализован на аппаратном уровне), но мы делаем это слева, а не справа.

Независимо от того, делаете ли вы это в битовых операциях, строках или как угодно, решать только вам. Если вы делаете это в битах, то наиболее эффективным способом может быть clz (или вызов эквивалентной функции в стиле hibit) на ~value: __builtin_clz, где это возможно. Но это деталь реализации.

Answer 3

Это решение изначально было в двоичном виде и преобразовано в обычную математику в соответствии с указанием запрашивающей стороны.

Это было бы более разумно, поскольку двоичное, по крайней мере, умножение на 2 и деление на 2 должно быть << 1 и >> 1 для скорости, сложения и вычитания, вероятно, не имеют значения, так или иначе.

Если вы передадите маску вместо nBits, и будете использовать битовое смещение вместо умножения или деления, и измените хвостовую рекурсию на цикл, это, вероятно, будет наиболее эффективным решением, которое вы найдете, так как при любом другом вызове это будет ничто но одно добавление, оно будет таким же медленным, как и решение Альнитака, один раз в 4, может быть, даже 8 вызовов.

int incrementBizarre(int initial, int nBits)
    // in the 3 bit example, this should create 100
    mask=2^(nBits-1)
    // This should only return true if the first (least significant) bit is not set
    // if initial is 011 and mask is 100
    //                3               4, bit is not set
    if(initial < mask)
        // If it was not, just set it and bail.
        return initial+ mask // 011 (3) + 100 (4) = 111 (7)
    else
        // it was set, are we at the most significant bit yet?
        // mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
        if(mask / 2) > 0
            // No, we were't, so unset it (initial-mask) and increment the next bit
            return incrementBizarre(initial - mask, mask/2)
        else
            // Whoops we were at the most significant bit.  Error condition
            throw new OverflowedMyBitsException()

Ух ты, получилось круто. Я не фигурировал в рекурсии до последней секунды там.

Кажется, что это неправильно - некоторые операции не должны работать, но они выполняются из-за характера того, что вы делаете (похоже, у вас могут возникнуть проблемы, когда вы работаете с битами и битами). слева не ноль, но оказывается, что вы никогда не сможете работать с битом, если все биты слева не равны нулю - это очень странное условие, но верно.

Пример потока от 110 до 001 (от 3 до 4 назад):

mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true;  initial + mask = 001--correct answer

Answer 4

Вот решение из моего ответа на другой вопрос , который вычисляет следующий перевернутый битовый индекс без зацикливания. Однако он сильно зависит от битовых операций.

Основная идея заключается в том, что при увеличении числа просто переворачивается последовательность младших битов, например, от nnnn0111 до nnnn1000. Таким образом, чтобы вычислить следующий перевернутый битовый индекс, вы должны перевернуть последовательность старших значащих битов. Если на вашей целевой платформе есть инструкция CTZ («считать конечные нули»), это можно сделать эффективно.

Пример на C с использованием GCC __builtin_ctz:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Compute a mask of LSBs.
        unsigned mask = i ^ (i + 1);
        // Length of the mask.
        unsigned len = __builtin_ctz(~mask);
        // Align the mask to MSB of n.
        mask <<= bits - len;
        // XOR with mask.
        j ^= mask;
    }
}

Без инструкции CTZ вы также можете использовать целочисленное деление:

void iter_reversed(unsigned bits) {
    unsigned n = 1 << bits;

    for (unsigned i = 0, j = 0; i < n; i++) {
        printf("%x\n", j);

        // Find least significant zero bit.
        unsigned bit = ~i & (i + 1);
        // Using division to bit-reverse a single bit.
        unsigned rev = (n / 2) / bit;
        // XOR with mask.
        j ^= (n - 1) & ~(rev - 1);
    }
}

Answer 5

Редактировать: Конечно, вопрос об оригинальном постере собирался сделать приращение (обратное), что делает вещи проще, чем добавление двух случайных значений. Так что ответ nwellnhof уже содержит алгоритм.

---

Суммирование двух значений обращения битов

Вот одно решение в php:

function RevSum ($a,$b) {

    // loop until our adder, $b, is zero
    while ($b) {

        // get carry (aka overflow) bit for every bit-location by AND-operation
        // 0 + 0 --> 00   no overflow, carry is "0"
        // 0 + 1 --> 01   no overflow, carry is "0"
        // 1 + 0 --> 01   no overflow, carry is "0"
        // 1 + 1 --> 10   overflow! carry is "1"

        $c = $a & $b;


        // do 1-bit addition for every bit location at once by XOR-operation
        // 0 + 0 --> 00   result = 0
        // 0 + 1 --> 01   result = 1
        // 1 + 0 --> 01   result = 1
        // 1 + 1 --> 10   result = 0 (ignored that "1", already taken care above)

        $a ^= $b;


        // now: shift carry bits to the next bit-locations to be added to $a in
        // next iteration.
        // PHP_INT_MAX here is used to ensure that the most-significant bit of the
        // $b will be cleared after shifting. see link in the side note below.

        $b = ($c >> 1) & PHP_INT_MAX;

    }

    return $a;
}

Примечание: см. этот вопрос о сдвиге отрицательных значений.

А что касается теста; начинать с нуля и увеличивать значение на 8-битное обратное значение (10000000):

$value = 0;
$add = 0x80;    // 10000000 <-- "one" as bit reversed

for ($count = 20; $count--;) {      // loop 20 times
    printf("%08b\n", $value);       // show value as 8-bit binary
    $value = RevSum($value, $add);  // do addition
}

... выведет:

 00000000
 10000000
 01000000
 11000000
 00100000
 10100000
 01100000
 11100000
 00010000
 10010000
 01010000
 11010000
 00110000
 10110000
 01110000
 11110000
 00001000
 10001000
 01001000
 11001000

Answer 6

Когда вы обращаетесь 0 to 2^n-1, но их битовая комбинация меняется, вы в значительной степени покрываете всю 0-2^n-1 последовательность

Sum = 2^n * (2^n+1)/2

O(1) операция. Нет необходимости делать битовые обращения

Answer 7

Как насчет добавления 1 к старшему значащему биту, а затем переноса к следующему (менее значимому) биту, если необходимо. Вы можете ускорить это, работая с байтами:

1. Предварительное вычисление таблицы поиска для обратного отсчета от 0 до 256 (00000000 -> 10000000, 10000000 -> 01000000, ..., 11111111 -> 00000000).
2. Установите все байты в вашем многобайтовом номере на ноль.
3. Увеличение старшего значащего байта с помощью таблицы поиска. Если байт равен 0, увеличить следующий байт, используя таблицу поиска. Если байт равен 0, увеличить следующий байт ...
4. Перейти к шагу 3.

Answer 8

Вот решение, которое на самом деле не пытается делать какие-либо дополнения, но использует шаблон включения / выключения последовательности (большинство битов сиг- нала чередуются каждый раз, следующий самый больший бит сиг- на меняется каждый раз и т. Д.), Настройте n как желательно:

#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)

int main() {
    int n   = 3;
    int max = (1 << n);
    int x   = 0;

    for(int i = 1; i <= max; ++i) {
        std::cout << x << std::endl;
        /* if n == 3, this next part is functionally equivalent to this:
         *
         * if((i % 1) == 0) FLIP(x, n - 1);
         * if((i % 2) == 0) FLIP(x, n - 2);
         * if((i % 4) == 0) FLIP(x, n - 3);
         */
        for(int j = 0; j < n; ++j) {
            if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
        }                       
    }
}

Answer 9

С n в качестве вашей степени 2 и х переменной, которую вы хотите шагнуть:

(defun inv-step (x n)       ; the following is a function declaration
  "returns a bit-inverse step of x, bounded by 2^n"    ; documentation
  (do ((i (expt 2 (- n 1))  ; loop, init of i
          (/ i 2))          ; stepping of i
       (s x))               ; init of s as x
      ((not (integerp i))   ; breaking condition
       s)                   ; returned value if all bits are 1 (is 0 then)
    (if (< s i)                         ; the loop's body: if s < i
        (return-from inv-step (+ s i))  ;     -> add i to s and return the result
        (decf s i))))                   ;     else: reduce s by i

Я прокомментировал это полностью, поскольку вы, возможно, не знакомы с этим синтаксисом.

edit : вот хвостовая рекурсивная версия. Это кажется немного быстрее, при условии, что у вас есть компилятор с оптимизацией хвостового вызова.

(defun inv-step (x n)
  (let ((i (expt 2 (- n 1))))
    (cond ((= n 1)
           (if (zerop x) 1 0))         ; this is really (logxor x 1)                                                 
          ((< x i)
           (+ x i))
          (t
           (inv-step (- x i) (- n 1))))))

Answer 10

Вот ответ на Perl. Вы не говорите, что следует за шаблоном «все единицы», поэтому я просто возвращаю ноль. Я убрал побитовые операции, чтобы их было легко перевести на другой язык.

sub reverse_increment {
  my($n, $bits) = @_;

  my $carry = 2**$bits;
  while($carry > 1) {
    $carry /= 2;
    if($carry > $n) {
      return $carry + $n;
    } else {
      $n -= $carry;
    }
  }
  return 0;
}