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

@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:

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@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