Подсчет, обратный битовый паттерн
https://stackoverflow.com/questions/259212
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь найти алгоритм для подсчета от 0 до 2 n -1, но их битовая комбинация поменялась местами. Я забочусь только о LSB слова. Как вы уже догадались, я потерпел неудачу.
Для n = 3:
000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7
Вы поняли идею.
Ответы в псевдокоде великолепны. Фрагменты кода на любом языке приветствуются, предпочтительны ответы без битовых операций.
Пожалуйста, не размещайте фрагмент без краткого объяснения или указателя на источник.
Изменить: я забыл добавить, у меня уже есть наивная реализация, которая просто инвертирует переменную count. В каком-то смысле этот метод на самом деле не считается.
Решение
Это, я думаю, проще всего с битовыми операциями, даже если вы сказали, что это не было предпочтительным
Предполагая 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 " is < = 16 или < = 8
Другие советы
На каждом шаге найдите крайнюю левую цифру 0 вашего значения. Установите его и очистите все цифры слева от него. Если вы не нашли цифру 0, значит, вы переполнились: верните 0, или остановите, или вылетите, или все, что вы хотите.
Это то, что происходит с обычным двоичным шагом (я имею в виду, что это эффект, а не то, как он реализован на аппаратном уровне), но мы делаем это слева, а не справа.
Делаете ли вы это в битовых операциях, строках или как угодно, решать только вам. Если вы делаете это в битах, то наиболее эффективным способом может быть clz (или вызов эквивалентной функции в стиле hibit) в ~value: __builtin_clz, где это возможно. Но это деталь реализации.
Изначально это решение было в двоичном виде и преобразовано в обычную математику, как указано в запросчике.
Это было бы более разумно в виде двоичного кода, по крайней мере умножение на 2 и деление на 2 должно быть < < 1 и & Gt; & Gt; 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
Вот решение из моего другого ответа. вопрос , который вычисляет следующий битовый индекс без зацикливания. Однако он сильно зависит от битовых операций.
Основная идея заключается в том, что при увеличении числа просто переворачивается последовательность младших битов, например, от nnnn0111 до nnnn1000. Таким образом, чтобы вычислить следующий перевернутый битовый индекс, вы должны перевернуть последовательность старших значащих битов. Если на вашей целевой платформе есть команда CTZ (& Quot; считать конечные нули & Quot;), это можно сделать эффективно.
Пример на 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);
}
}
void reverse(int nMaxVal, int nBits)
{
int thisVal, bit, out;
// Calculate for each value from 0 to nMaxVal.
for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
{
out = 0;
// Shift each bit from thisVal into out, in reverse order.
for (bit=0; bit<nBits; ++bit)
out = (out<<1) + ((thisVal>>bit) & 1)
}
printf("%d -> %d\n", thisVal, out);
}
Может увеличиваться от 0 до N (" обычный " way ") и делать ReverseBitOrder () для каждой итерации. Вы можете найти несколько реализаций здесь (мне нравится LUT, Лучший). Должно быть очень быстро.
Вот ответ на 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;
}
Вот решение, которое на самом деле не пытается делать какие-либо дополнения, но использует шаблон включения / выключения последовательности (большинство битов сиг- нала чередуются каждый раз, следующий самый больший бит сиг- на меняется каждый раз и т. д.), настройте 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));
}
}
}
Как насчет добавления 1 к старшему значащему биту, а затем переноса к следующему (менее значимому) биту, если необходимо. Вы можете ускорить это, работая с байтами:
<Ол>С n в качестве степени 2 и x с переменной, которую вы хотите изменить:
(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))))))
Когда вы переворачиваете 0 to 2^n-1, но их битовый паттерн перевернут, вы в значительной степени покрываете всю 0-2^n-1 последовательность
Sum = 2^n * (2^n+1)/2
O(1) операция. Нет необходимости делать битовые обращения
Редактировать: Конечно, вопрос об оригинальном постере собирался сделать приращение (обратное), что делает вещи проще, чем добавление двух случайных значений. Итак, ответ 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
