Объединение двухбитных паттернов - PullRequest
Новая
       14

Объединение двухбитных паттернов

3 голосов
/ 20 марта 2011

Мне нужно объединить две переменные. Они оба без подписи.

  • Первый: 11000000
  • Второй: 11111010000

Желаемый выход: 11011111010000

Словами: мне нужно поставить все 1, а затем один 0 (в первом числе) перед целым вторым числом. Единственная мысль, которая приходит мне в голову, это сдвинуть первое число влево на столько, сколько длина второго. И чем суммировать. Но я не знаю длины. Хотя это, вероятно, можно найти, разве нет лучшего способа проще?

Thx

Ответы [ 3 ]

2 голосов
/ 20 марта 2011

Вот решение, которое работает в постоянное время:

Вы можете вычислить позицию первого 1 бита x с помощью (int) (log (x) / log (2)).

Кроме того, вы можете вычислить число конечных нулей x с помощью хитрого трюка, показанного здесь: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

Следовательно, ваша программа может выглядеть примерно так: 

int x, y;
int lookuptable[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25,
                        17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 
                        12, 18, 6, 11, 5, 10, 9 };

int tail_x = lookuptable[(((x & -x) * 0x077CB531U)) >> 27];
int size_y = (int)(log(y) / log(2)) + 1;

if (tail_x - size_y <= 0) {
        x <<= size_y - tail_x + 1;
} else {
        x >>= tail_x - size_y - 1;
}       

x |= y;

Теперь x содержит результат добавления y к x, как указано в OP. Обратите внимание, что для 32-битных компьютеров вам необходимо внести небольшие изменения.

1 голос
/ 20 марта 2011

бит сдвигайте первый вправо до тех пор, пока у вас не будет серии 1 без конечного 0. затем бит сдвиньте его влево для «длины» второго плюс 1 (на самом деле количество битов после и включая первый1) а затем ИЛИ их вместе, не суммируйте, иначе могут возникнуть ошибки.

0 голосов
/ 20 марта 2011

Определение, является ли целое число степенью 2

без знака int v; // мы хотим увидеть, является ли v степенью 2 bool f; // результат идет сюда

f = (v & (v - 1)) == 0; Обратите внимание, что 0 неправильно считается степенью 2 здесь. Чтобы исправить это, используйте: f = v &&! (v & (v - 1));

чтобы увидеть, что v на 1 меньше степени 2, добавим единицу к v (v + 1) & v) == 0

(копировать + 1) и копировать)! = 0

поэтому, используя ответ Джона и заменяя copy! = 0 на (copy + 1) & copy)! = 0 будет обрезать, пока не будет INT с серией 1 в конце. область действия копии должна быть за пределами цикла for, и результат будет (copy << (cBitsFirst + 1)) | второй; </p> 

unsigned int first, second; // initialize these somehow
unsigned int result = 0;
int cBitsFirst = 0;
unsigned int copy;
for (copy; (copy + 1) & copy) != 0; copy >>= 1) {//stop when there is series of 0's followed by a series of 1's
    ++cBitsFirst;
}

result = (copy << (log2(second)+1) | second;//the plus one gives the 0 back
...