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

Question

Например, если у меня есть номер 0101 1111, и я хочу сдвигать каждый 4-битный раздел влево, чтобы получить 1010 1110. Хотя я мог бы просто модулировать каждый раздел, чтобы получить два 4-битных числа, есть ли алгоритм, который не должен этого делать?

Answer 1

Наивный подход

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

(((x & 0xf)          // take only 4 bits
    << 1)            // shift them by 1
       & 0xf)        // get rid of potential overflow    

Для n + 1-й группы из 4 бит это

(((x & (0xf<<(n*4)))
    << 1)
      & (0xf<<(n*4)))

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

Менее наивный подход

Другой подход - просто сдвинуть full x на 1, что приводит к одновременному смещению каждой 4-битной группы:

0101 1111  -> 1011 1110

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

   1011 1110 
 & 1110 1110
   ---------
   1010 1110

1110 равно e в шестнадцатеричном формате. Итак, вам нужно сгенерировать число с таким количеством 0xe, сколько имеется 4-битных сегментов. В вашем случае это 0xee, если это всего 8 бит. Это 0xeeeeeeeeeeeeeeee, если это 64 бита. Кто-то сказал этот ответ в комментариях. Здесь у вас есть объяснение.

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

Answer 2

Вот один способ.

int bits = 0b1111_0001_0011_0111;
int result = 0;
int m = 0b1111;
while(m != 0) {
    result |= ((bits & m) << 1) & m;
    m <<= 4;
}
System.out.printf("%-7s = %s%n","src", Integer.toBinaryString(bits));
System.out.printf("%-7s = %s%n","result", Integer.toBinaryString(result));

Печать

src     = 1111000100110111
result  = 1110001001101110