URL: https://www.opennet.me/cgi-bin/openforum/vsluhboard.cgi
Форум: vsluhforumID9
Нить номер: 9471
[ Назад ]

Исходное сообщение
"pretty bitwise operations"

Отправлено handler2006 , 31-Май-12 01:13 
Здравствуйте!
Дано: Двухбайтовая битовая маска.
Задача: сравнить биты данной маски (к примеру, 13-ый и 14-ый).
Решение:

unsigned short bitMask = 0x6000; // (0110 0000 0000 0000)
int bitFlag = 3; // (0000 0000 0000 0000 0000 0000 0000 0011) in 32-bit arch
// todo
if ( (bitMask&(bitFlag<<13))>>13 == bitFlag )
{
  // bits are proprietary
}

На мой взгляд, конструкция корявая (сдвинули, сложили, опять сдвинули, потом сравнили результат с эталонным). Тем более в большом проекте такая конструкция будет вводить в ступор программистов.
Возможно, существуют более изящные приемы работы с битовыми массивами?
Спасибо.
Алексей

Содержание

Сообщения в этом обсуждении
"pretty bitwise operations"
Отправлено Alex_S , 31-Май-12 04:46 
>[оверквотинг удален]
> {
>   // bits are proprietary
> }
>

> На мой взгляд, конструкция корявая (сдвинули, сложили, опять сдвинули, потом сравнили результат
> с эталонным). Тем более в большом проекте такая конструкция будет вводить
> в ступор программистов.
> Возможно, существуют более изящные приемы работы с битовыми массивами?
> Спасибо.
> Алексей

два бита удобно сравнивать xor-ом - он дает нуль, если биты одинаковые

  то есть у тебя условие будет типа( (1<<pos1) & bitmask) ^ ( (1 <<pos2) & bitmask )


"pretty bitwise operations"
Отправлено pavlinux , 01-Июн-12 01:10 
Курсовая, зачёт?

 
if ((bitMask >> 13) & bitFlag )  // так вполне хватает

---
Ща найду полезную сцылку...


"pretty bitwise operations"
Отправлено pavlinux , 01-Июн-12 01:54 
> Ща найду полезную сцылку...

Во - http://graphics.stanford.edu/~seander/bithacks.html


"pretty bitwise operations"
Отправлено pavlinux , 02-Июн-12 04:21 
> Курсовая, зачёт?
>
 
> if ((bitMask >> 13) & bitFlag )  // так вполне хватает
>

Кстати, пофеншую - с маской сравнивают, а не двигают её!

 
if ((bitFlag << 13) & bitMask)  // так феншуйнее.


"pretty bitwise operations"
Отправлено handler2006 , 02-Июн-12 05:34 
Собственно, последний вариант и использую в "курсовой". А статья действительно хорошая. Спасибо.
Только немного так:

unsigned mask; // input bitmask
unsigned flag; // given checked mask
unsigned bits;
if (mask^(flag<<bits))
{
// all flag's bits are equal to mask
}


"pretty bitwise operations"
Отправлено pavlinux , 02-Июн-12 15:57 
> Только немного так:
> if (mask^(flag<<bits))
> {
>  // all flag's bits are equal to mask
> }
>

(mask ^(flag << bits)) == FALSE,

XOR даёт 1 (TRUE) если биты разные!!!

И ваще, вот эти 4 таблицы надо наизусть знать, иначе препод расстреляет.


  AND            OR            XOR           NOT
0 & 0 = 0     0 | 0 = 0     0 ^ 0 = 0      ~0 = 1
0 & 1 = 0     0 | 1 = 1     0 ^ 1 = 1      ~1 = 0
1 & 0 = 0     1 | 0 = 1     1 ^ 0 = 1
1 & 1 = 1     1 | 1 = 1     1 ^ 1 = 0


"pretty bitwise operations"
Отправлено handler2006 , 02-Июн-12 18:29 
Полностью с Вами согласен, и дело даже не в преподавателях - за этот проект мне платят деньги (на работе), но я только еще учусь. XOR в данном случае даст true , если все проверяемые биты совпали и false - если хоть один бит не совпал, что отвечает Вашему замечанию. Однако в моем коде проверяется условие на true - видимо в теле условия мне необходимо выполнить действия, соответствующие несовпадению по маске - я просто неправильно описал алгоритьм в примере.

"pretty bitwise operations"
Отправлено pavlinux , 02-Июн-12 20:38 
> видимо в теле условия мне необходимо выполнить действия, соответствующие несовпадению по маске

Не совпадут с маской ВСЕ, кроме маски :)


"pretty bitwise operations"
Отправлено handler2006 , 02-Июн-12 22:33 
Каюсь

"pretty bitwise operations"
Отправлено Alex_S , 04-Июн-12 06:11 
>> Курсовая, зачёт?
>>
 
>> if ((bitMask >> 13) & bitFlag )  // так вполне хватает
>>

> Кстати, пофеншую - с маской сравнивают, а не двигают её!
>
 
> if ((bitFlag << 13) & bitMask)  // так феншуйнее.
>

херовый у вас фэншуй.

  по-хорошему, на рантайме ничего никуда сдвигать вообще не надо,
а надо иметь уже сдвинутое значение и с ним уже делать and/xor/whatever


"pretty bitwise operations"
Отправлено handler2006 , 04-Июн-12 06:47 
Дано: двухбайтовая битовая маска (набор из 16 битов)
Задача: проверить на соответствие 13-ый и 14-ый бит (считывается из конфига в виде, допустим, тоже двухбайтового числа, принимаемого значения 0, 1, 2 и 3).
Ваши предложения?

"pretty bitwise operations"
Отправлено LSTemp , 04-Июн-12 15:04 
> Дано: двухбайтовая битовая маска (набор из 16 битов)
> Задача: проверить на соответствие 13-ый и 14-ый бит (считывается из конфига в
> виде, допустим, тоже двухбайтового числа, принимаемого значения 0, 1, 2 и
> 3).
> Ваши предложения?

((mask XOR value) AND 0xFFFF) = 0 - совпало

0xFFFF заменяется на маску сравниваемых битов (в поставленной задаче - биты 13-14). что проще?
делаем XOR, потом отсекаем ненужные биты в результате.



"pretty bitwise operations"
Отправлено pavlinux , 04-Июн-12 15:14 
> ((mask XOR value) AND 0xFFFF) = 0 - совпало

SHL/SHR работают быстрее XOR


"pretty bitwise operations"
Отправлено LSTemp , 04-Июн-12 15:57 
>> ((mask XOR value) AND 0xFFFF) = 0 - совпало
> SHL/SHR работают быстрее XOR

Кто бы спорил. Просто дал альтернативный псевдокод.

Так, что если смотреть сколько машинных тактов, занимает выполнение конкретной команды, то Вы правы на все 100%. Если быть чуть ближе к реальности, то мой вариант тоже вполне жизнеспособен.

PS
к тому же если внимательно вчитаться в начальный вопрос, на который я и отвечал:
"
Здравствуйте!
Дано: Двухбайтовая битовая маска.
Задача: сравнить биты данной маски (к примеру, 13-ый и 14-ый).
Решение:
"

то там нигде не сказано, что в маске не будет "паразитных" битов с неизвестным значением. требуется только сравнить 13-14 бит полученной маски (читай - случайное значение) с данными. простой сдвиг в этом случае, как с "точной" маской не прокатит.

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



"pretty bitwise operations"
Отправлено pavlinux , 04-Июн-12 22:18 
> Фактически, вопрос поставлен так, что ...

Фактически, вопрос был: как упростить (A & ( B << C )) >> C == D ) :)


"pretty bitwise operations"
Отправлено LSTemp , 13-Июн-12 16:19 
>> Фактически, вопрос поставлен так, что ...
> Фактически, вопрос был: как упростить (A & ( B << C ))
> >> C == D ) :)

+1000

чувствую себя идиотом.



"pretty bitwise operations"
Отправлено Alex_S , 06-Июн-12 05:27 
> PS
> к тому же если внимательно вчитаться в начальный вопрос, на который я
> и отвечал:
> "
> Здравствуйте!
> Дано: Двухбайтовая битовая маска.
> Задача: сравнить биты данной маски (к примеру, 13-ый и 14-ый).
> Решение:

  вообще вопрос можно было понять как "одинаковы ли значения 13 и 14 бита в маске"


> с неизвестным значением. требуется только сравнить 13-14 бит полученной маски (читай
> - случайное значение) с данными.

  правильная постановка вопроса, имхо - "установлены ли в данной маске одновременно биты 13 и 14"

   если позиции 13 и 14 жестко заданы и не меняются на рантайме - тогда вообще никаких сдвигов не надо
  
   #define  LOVELY_BIT_MASK  ((1<<13) | (1<<14))

   if ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK)  - вполне покатит

   если маска однобитная - то и сравнивать не надо


"pretty bitwise operations"
Отправлено pavlinux , 06-Июн-12 18:02 
>[оверквотинг удален]
>> с неизвестным значением. требуется только сравнить 13-14 бит полученной маски (читай
>> - случайное значение) с данными.
>   правильная постановка вопроса, имхо - "установлены ли в данной маске
> одновременно биты 13 и 14"
>    если позиции 13 и 14 жестко заданы и не
> меняются на рантайме - тогда вообще никаких сдвигов не надо
>    #define  LOVELY_BIT_MASK  ((1<<13) | (1<<14))
>    if ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK)  -
> вполне покатит
>    если маска однобитная - то и сравнивать не надо


#define  LOVELY_BITMASK  ((1<<13) | (1<<14))

const int our_mask = 0b0011000000000000;
const int bitFlag  = 0b0011;

inline int love(void) {

        return ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK);
}

inline int shr_and(void) {

        return ( (our_mask >> 13 ) & bitFlag);
}

# gcc -O0 test.c
# objdump -d test.o


0000000000000000 <love>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   8b 05 00 00 00 00       mov    0x0(%rip),%eax        # a <love+0xa>
   a:   25 00 60 00 00          and    $0x6000,%eax
   f:   3d 00 60 00 00          cmp    $0x6000,%eax
  14:   0f 94 c0                sete   %al
  17:   0f b6 c0                movzbl %al,%eax
  1a:   5d                      pop    %rbp
  1b:   c3                      retq  

000000000000001c <shr_and>:
  1c:   55                      push   %rbp
  1d:   48 89 e5                mov    %rsp,%rbp
  20:   8b 05 00 00 00 00       mov    0x0(%rip),%eax        # 26 <shr_and+0xa>
  26:   89 c2                   mov    %eax,%edx
  28:   c1 fa 0d                sar    $0xd,%edx
  2b:   8b 05 00 00 00 00       mov    0x0(%rip),%eax        # 31 <shr_and+0x15>
  31:   21 d0                   and    %edx,%eax
  33:   5d                      pop    %rbp
  34:   c3                      retq  

# gcc -Ofast test.c
# objdump -d test.o


0000000000000000 <love>:
   0:   31 c0                   xor    %eax,%eax
   2:   c3                      retq  
   3:   66 66 66 66 2e 0f 1f    data32 data32 data32 nopw %cs:0x0(%rax,%rax,1)
   a:   84 00 00 00 00 00

0000000000000010 <shr_and>:
  10:   b8 01 00 00 00          mov    $0x1,%eax
  15:   c3                      retq  


"pretty bitwise operations"
Отправлено LSTemp , 13-Июн-12 16:05 
>
 
> inline int shr_and(void) {
>         return ( (our_mask >>
> 13 ) & bitFlag);
> }
>

так не прокатит, хотя идея ясна. надо так видимо (в терминах автора):

((bitMask >> 12 ) == bitFlag);


"pretty bitwise operations"
Отправлено pavlinux , 06-Июн-12 18:28 
>    #define  LOVELY_BIT_MASK  ((1<<13) | (1<<14))
>    if ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK)  -

" == LOVELY_BITMASK " - лишнее.


"pretty bitwise operations"
Отправлено Alex_S , 08-Июн-12 05:08 
>>    #define  LOVELY_BIT_MASK  ((1<<13) | (1<<14))
>>    if ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK)  -
> " == LOVELY_BITMASK " - лишнее.

  неа .  если 2 бита надо - не лишнее
  иначе может сработать по одному биту
  


"pretty bitwise operations"
Отправлено LSTemp , 13-Июн-12 15:50 
>> PS
>> к тому же если внимательно вчитаться в начальный вопрос, на который я
>> и отвечал:
>> "
>> Здравствуйте!
>> Дано: Двухбайтовая битовая маска.
>> Задача: сравнить биты данной маски (к примеру, 13-ый и 14-ый).
>> Решение:
>   вообще вопрос можно было понять как "одинаковы ли значения 13
> и 14 бита в маске"

тогда скорее уж как (если смотреть код автора) установлены ли биты маски (bitMask) 13 и 14 в заданное значение (bitFlag).

ИМХО не знаю кто там такой умный - препод или студент, что путает определение данных, масок и флагов.

>[оверквотинг удален]
>> с неизвестным значением. требуется только сравнить 13-14 бит полученной маски (читай
>> - случайное значение) с данными.
>   правильная постановка вопроса, имхо - "установлены ли в данной маске
> одновременно биты 13 и 14"
>    если позиции 13 и 14 жестко заданы и не
> меняются на рантайме - тогда вообще никаких сдвигов не надо
>    #define  LOVELY_BIT_MASK  ((1<<13) | (1<<14))
>    if ( (our_mask & LOVELY_BITMASK) == LOVELY_BITMASK)  -
> вполне покатит
>    если маска однобитная - то и сравнивать не надо


"pretty bitwise operations"
Отправлено pavlinux , 04-Июн-12 14:15 
>  херовый у вас фэншуй.
> а надо иметь уже сдвинутое значение

А кто это значение должен "уже сдвинуть"? Само? :)


"pretty bitwise operations"
Отправлено Alex_S , 06-Июн-12 05:28 
>>  херовый у вас фэншуй.
>> а надо иметь уже сдвинутое значение
> А кто это значение должен "уже сдвинуть"? Само? :)

  компилятор. дефайны. сюрприз ?

  хотя для динамически вычисляемых масок не катит, конечно же..