Как эффективно заменить непрерывный набор бит - PullRequest
Новая
       18

Как эффективно заменить непрерывный набор бит

0 голосов
/ 02 ноября 2019

Допустим, у меня есть двоичное число 1001100, и я хочу заменить его на 1011 в разделе [2, 6).

Это будет выглядеть примерно так: 

Binary: 1001100
Sub:    --1011-
Result: 1010110

Я знаю, что можно многократно устанавливать один бит несколько раз, используя этот код:
number |= 1UL << n;

Но мне было интересно, есть ли способ вообще добиться этого более эффективным способом.

Ответы [ 2 ]

2 голосов
/ 02 ноября 2019

Давайте рассмотрим более общую проблему: у вас есть двоичное число a , и вы хотите заменить его биты на биты другого числа b , только когда соответствующий бит третьегочисло m равно единице.

Для вашей конкретной задачи: 

a = 1001100
b = xx1011x
m = 0011110

, но нет необходимости, чтобы m соответствовал одному диапазону.

Псевдокод для вычисления результата r будет 

for all i in 0 to 6
  if m[i]=1
     r[i]=a[i]
  else
    r[i]=b[i]

или эквивалентно 

for all i in 0 to 6
  r[i] = (a[i] and (m[i]=1)) or (b[i] and (m[i]=0))

Из этого легко сделать вывод, чтоцикл бесполезен, и выражение 

r = (a & m) | (b & ~m)

дает правильный результат.

Обратите внимание, что если вы хотите произвести замену в определенном диапазоне k to l (например, от 1 до 5 в вашем случае), маска будет (2 ^ l - 1) - (2 ^ k - 1) = 2 ^ l - 2 ^ k

Так вот соответствующий код C 

unsigned int replace_bit(unsigned int a, unsigned int b, int k, int l){
  unsigned int mask=(1<<l) - (1<<k)
  return  (a & mask) | (b & ~mask) ;
}
1 голос
/ 02 ноября 2019

Наиболее эффективный способ в архитектуре x86 - использование инструкции PDEP , которая эквивалентна 32-битному эквиваленту 

PDEP: unsigned __int32 _pdep_u32(unsigned __int32 src, unsigned __int32 mask);

Идея ее использования 

mov  ebx, 1001100b    ; initial value
mov  ecx, 0011110b    ; mask value (=SRC2) - bits to be replaced
mov  edx, 0001011b    ; bits to be inserted (=SRC1) at positions ECX
mov  eax, ecx         ; duplicate mask to EAX
not  eax              ; invert mask
and  ebx, eax         ; mask out bits that will be modified
pdep eax, edx, ecx    ; put bits from ECX to position specified by EDX into EAX
or   eax, ebx         ; merge masked initial value with result of PDEP
==>                   ; result is in EAX

Это решение для сборки x86.
При необходимости преобразуйте его во внутреннее представление.
Имейте в виду, что PDEP довольно медленно на процессорах AMD.
Это решение работает без каких-либоусловные операции типа прыжков.

...