Битовые операции

@stawerfar · Регистрация: 14.12.2010

Студворк — интернет-сервис помощи студентам

Всем привет! Помогите решить интересную задачу! Нужно ниже указный код переписать без условных операторов используя только битовые операции т.е & | ^ ~ << >>. Дополнительных переменных добавлять нельзя, так же нельзя использовать массивы.

C
1
2
3
4
5
6
7
8
9
/* значения a,value1,result1,result2 задаются пользователем */
if ( a == value1)
{
  b = result1;
}
else
{
 b = result2;
}

Подскажите пожалуйста, как это организовать!? Я только додумался вот до этого:

C
1
2
register m[]={result1,result2};
b = m[!!(a ^ value1)];

Но это не совсем правильно, так как я использовал массивы.

@Thinker · 18.07.2013, 14:24

ну, 0 и 1 мы получим, а дальше? если имеется умножение, то все просто, иначе большие выражения всплывут, и то, если мы разрядность знаем.

@SatanaXIII · 18.07.2013, 14:42

Можно ли использовать циклы?

Я остановился на том, что нужно использовать выражение типа
(~(~a & v) & r1 )
которое даст нам result1, если a и value1 равны. В противном случае оно нам даст разницу меж всеми тремя. И как-то надо прикрутить к нему вторую часть, исключающую эту разницу и, при этом, добавляющую result2, если значения условия не равны.
Просто мысль. Сочинить запись я не смог.

@stawerfar · 18.07.2013, 18:10 **[ТС]**

Нет циклов не должно быть! Вообще необходимо реализовать более быструю альтернативы условным операторам if и else if и else

Добавлено через 2 часа 36 минут
Вот реализовал что говаривал Thinker!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
 
template <class type>
int showbin(type &v)
{
    int bitsize = sizeof(type) * 8;
   int i = 0;
   
   for (i = bitsize - 1; i >=0; --i)
   {
    std::cout << !!(v & 1 << i);
   }
   std::cout << std::endl;
   return 0;
}
 
int main(void)
{
 
    unsigned char a = 5, // входящее значение
                          value1 = 5, // значение с чем сравнивать if (a == value1)
                          c = 0, // переменная для выражения ~(a ^ value1)
                          d = 0, // переменная для выражения (a ^ value1)
                         return1 = 10, // значение присваиваемое b если  a == value1
                         return2 =  5, // значение присваимваемое b если a != value1
                          b = 0; // выходящее значение
 
   c = ~(a ^ value1);
   
   c = !!(c & (1 << 0)) & 
         !!(c & (1 << 1)) & 
         !!(c & (1 << 2)) & 
         !!(c & (1 << 3)) & 
         !!(c & (1 << 4)) & 
         !!(c & (1 << 5)) & 
         !!(c & (1 << 6)) & 
         !!(c & (1 << 7));
    
    c = (c | (c << 0) & (c & (1 << 0)) << 0) | 
          (c | (c << 1) & (c & (1 << 0)) << 1) | 
          (c | (c << 2) & (c & (1 << 0)) << 2) |
          (c | (c << 3) & (c & (1 << 0)) << 3) |
          (c | (c << 4) & (c & (1 << 0)) << 4) |
          (c | (c << 5) & (c & (1 << 0)) << 5) |
          (c | (c << 6) & (c & (1 << 0)) << 6) |
          (c | (c << 7) & (c & (1 << 0)) << 7);
 
    d = (a ^ value1);
 
    d = !!(d & (1 << 0)) | 
         !!(d & (1 << 1)) | 
         !!(d & (1 << 2)) | 
         !!(d & (1 << 3)) | 
         !!(d & (1 << 4)) | 
         !!(d & (1 << 5)) | 
         !!(d & (1 << 6)) | 
         !!(d & (1 << 7));
 
   d = (d | (d << 0) & (d & (1 << 0)) << 0) | 
          (d | (d << 1) & (d & (1 << 0)) << 1) | 
          (d | (d << 2) & (d & (1 << 0)) << 2) |
          (d | (d << 3) & (d & (1 << 0)) << 3) |
          (d | (d << 4) & (d & (1 << 0)) << 4) |
          (d | (d << 5) & (d & (1 << 0)) << 5) |
          (d | (d << 6) & (d & (1 << 0)) << 6) |
          (d | (d << 7) & (d & (1 << 0)) << 7);
    
    
    b = c & return1  | d & return2;
 
    showbin(c);
    showbin(d);
   showbin(b);
   std::cout << static_cast<int>(b) << std::endl;
   
   return 0;
}

Еще раз большое спасибо за инфу!

Evg · 18.07.2013, 18:20

Что-то мне кажется, что тут излишне сложные решения:

C
#include <stdio.h>
 
/* Оригинальная функция (для проверки) */
int func1 (int a, int value1, int result1, int result2)
{
  int b;
 
  if (a == value1)
    b = result1;
  else
    b = result2;
 
  return b;
}
 
/* Переписанная функция */
int func2 (int a, int value1, int result1, int result2)
{
  int b;
 
  /* Операция !x в Си всегда будет возвращать либо 1 (если x == 0),
   * либо 0 (если x !=0 ). Такой операцией мы легко вычислим признак,
   * равны между собой две переменные, или нет */
  int is_equal = ! (a - value1);
 
  /* А если на основании признака нужно вернуть первое или второе
   * значение, то это делается обычным взвешенным выражением,
   * коэффициэнты которого будут либо (1, 0), либо (0, 1) */
  b = is_equal * result1 + (1 - is_equal) * result2;
 
  return b;
}
 
int main (void)
{
  printf ("%d\n", func1 (5, 6, -1, 2));
  printf ("%d\n", func1 (5, 5, -1, 2));
 
  printf ("%d\n", func2 (5, 6, -1, 2));
  printf ("%d\n", func2 (5, 5, -1, 2));
 
  return 0;
}

Добавлено через 41 секунду
Ой я дятел.... условие невнимательно прочитал

@Thinker · 18.07.2013, 18:50

Сообщение от stawerfar

Вот реализовал что говаривал Thinker!

я немного другое говорил. можно меньше использовать битовые операции и совсем не нужно использовать !. Немного подправил ваш код:

C++
1
2
3
4
5
6
7
8
   c = ~(a ^ value1);
   c = (c & 1) & ((c >> 1) & 1) & ((c >> 2) & 1) & ((c >> 3) & 1) & ((c >> 4) & 1) & ((c >> 5) & 1) & ((c >> 6) & 1) & ((c >> 7) & 1);
   c = c | (c << 1) | (c << 2) | (c << 3) | (c << 4) | (c << 5) | (c << 6) | (c << 7); 
 
   d = a ^ value1;
   d = (d & 1) | ((d >> 1) & 1) | ((d >> 2) & 1) | ((d >> 3) & 1) | ((d >> 4) & 1) | ((d >> 5) & 1) | ((d >> 6) & 1) | ((d >> 7) & 1);
   d = d | (d << 1) | (d << 2) | (d << 3) | (d << 4) | (d << 5) | (d << 6) | (d << 7); 
   b = c & return1  | d & return2;

ValeryS · 18.07.2013, 19:24

вот решил для байта если размерность числа разная то без цикла не обойтись(по моему)

C++
1
2
3
4
5
6
7
unsigned char tmp =a^value;
                char tmp1 =tmp&0x80|tmp<<1& 0x80| tmp<<2&0x80 |tmp<<3& 0x80 |
                             tmp<<4&0x80 |tmp<<5& 0x80| tmp<<6&0x80 |tmp<<7& 0x80;
//tmp1=0x80 если a не равно value и 0 если равно
unsigned char tmp2=tmp1>>7;
//tmp2=0xFF если a не равно value и 0 если равно
b=result1&~tmp2 | result2&tmp2;

правда не проверял, так мысли вслух, с приоритетами мог наврать

Добавлено через 4 минуты

Сообщение от stawerfar

Вообще необходимо реализовать более быструю альтернативы условным операторам if и else if и else

а почему тогда нельзя использовать || && b и сравнение, от них скорость не падает
поскольку ветвления нет
вот так будет гораздо проще

C++
1
2
tmp = (a!=value)*-1;
b=result1&~tmp | result2&tmp;

Добавлено через 2 минуты
или даже так

C++
1
b=result1*(a==value) | result2*(a!=value);

Добавлено через 15 минут

Сообщение от Thinker

c = c | (c << 1) | (c << 2) | (c << 3) | (c << 4) | (c << 5) | (c << 6) | (c << 7);

а вот если бы привел к знаковому и загнал бы к старшему биту то не пришлось бы это писать
сдвиг вправо для знаковых и беззнаковых отличается
али забыл

@Thinker · 18.07.2013, 19:30

ValeryS, сдвиг отличается в одном случае:
сдвиг вправо отрицательного числа.
Только причем тут это? алгоритм работает для любых чисел (со знаком и без), все учтено

у нас в c либо 0, либо 1. нам либо 0...0 надо получить, либо 1...1.

ValeryS · 18.07.2013, 19:35

Сообщение от Thinker

ValeryS, сдвиг отличается в одном случае:
сдвиг вправо отрицательного числа.

ну я тебе про это же

Сообщение от Thinker

Только причем тут это?

ну смотри
вот у тебя

Сообщение от Thinker

c = (c & 1) & ((c >> 1) & 1) & ((c >> 2) & 1) & ((c >> 3) & 1) & ((c >> 4) & 1) & ((c >> 5) & 1) & ((c >> 6) & 1) & ((c >> 7) & 1);
c = c | (c << 1) | (c << 2) | (c << 3) | (c << 4) | (c << 5) | (c << 6) | (c << 7);

вот у меня

Сообщение от ValeryS

результат один и тот же 0 или 0xFF
но у меня сдвиг во второй строчке проще
загоняем все биты в старший
в результате получаем или 0 или -128 (0x80)
потом разом сдвигаем на семь и получаем или 0 или -1(0xFF)
а в остальном параллельно думаем

@Thinker · 18.07.2013, 19:42

Не по теме:

понял твой трюк, молодец :good:

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	18.07.2013, 14:24
	ну, 0 и 1 мы получим, а дальше? если имеется умножение, то все просто, иначе большие выражения всплывут, и то, если мы разрядность знаем. 1

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	18.07.2013, 14:42
	Можно ли использовать циклы? Я остановился на том, что нужно использовать выражение типа (~(~a & v) & r1 ) которое даст нам result1, если a и value1 равны. В противном случае оно нам даст разницу меж всеми тремя. И как-то надо прикрутить к нему вторую часть, исключающую эту разницу и, при этом, добавляющую result2, если значения условия не равны. Просто мысль. Сочинить запись я не смог. 1

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	18.07.2013, 19:30
	ValeryS, сдвиг отличается в одном случае: сдвиг вправо отрицательного числа. Только причем тут это? алгоритм работает для любых чисел (со знаком и без), все учтено у нас в c либо 0, либо 1. нам либо 0...0 надо получить, либо 1...1. 1

@Thinker
	18.07.2013, 19:42
	Не по теме: понял твой трюк, молодец :good: 1