Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
#1

Битовые операции - C++

18.07.2013, 11:18. Просмотров 1102. Ответов 28
Метки нет (Все метки)

Всем привет! Помогите решить интересную задачу! Нужно ниже указный код переписать без условных операторов используя только битовые операции т.е & | ^ ~ << >>. Дополнительных переменных добавлять нельзя, так же нельзя использовать массивы.
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)];
Но это не совсем правильно, так как я использовал массивы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.07.2013, 11:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Битовые операции (C++):

Битовые операции, битовые поля. - C++
Здравствуйте! Еслть 4 диапазона чисел: 0-100, 0-100, 0-6000, 0-3. Сделать в виде битовых операций. Записать в unsigned int. Использовать...

Битовые операции и операции смещения языка С - C++
Доброго времени суток господа,помогите пожалуйста.Есть 2 кода к задаче,первый работает верно(переводит обычные числа в 16-ти ричные),а...

Битовые операции - C++
Ребят, нужен алгоритм, а желательно и код для реализации следующей функции: Есть скажем числа от 0 до 7, т.е. 8 (2^3) Теперь...

Битовые операции - C++
Ребят, помогите кто чем может. Дана строка unsigned char. Необходимо через каждых 4 бита вставить 1, при этом ничего не затерев. ...

Битовые операции - C++
Собсно,если используется 4 байтовая переменная,то почему она представлена 16 битами(1010 0110 0010 0110),а не 32 битами?

Битовые операции - C++
Вот такая вот лаба на С, уже как не думал ну не могу решить я ее. Прошу помочь, прикрепил полное задание с примером работы(в примере...

28
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 13:40 #16
было бы за что дополнительно пришлось * и ! использовать, без этого выражение просто огромным получится.
1
stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
18.07.2013, 13:43  [ТС] #17
Если есть время, могли бы показать это "огромное выражение" мне для лучшего понимания битовой логики!
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 14:08 #18
лучше поясню в чем будет смыл. Для простоты переобозначу переменные так:
C++
1
rezult = (a == b) ? x : y;
так вот, предположим, что мы знаем разрядность всех переменных и она равна n.

a==b тогда и только тогда, когда ~(a^b) == 1...1 (все n единичек)

1. шаг.
Обозначим (временно) A = ~(a^b). Выделим в A все биты:
A & 1, (A >> 1) & 1,..., (A >> (n-1)) & 1
и ко всем выделенным битам применим операцию &:
AA = (A & 1) & ... & ((A >> (n-1)) & 1)

так вот если a==b, то AA == 1, иначе AA == 0.

Далее младший бит в AA ставим на все остальные позиции:
AAA = (AA & 1) | ((AA & 1) << 1) | ... | ((AA & 1) << (n-1))
получим число 1...1 (число из всех единиц), если a==b, либо 0...0 (если a не равно b).
к полученному числу и x применяем &.

Половина выражения закончена, результатом которого будет либо x, либо 0.

2. шаг. Пусть B = (a^b)
ко всем выделенным битам числа B применим операцию |:
BB = (B & 1) | ... | ((B >> (n-1)) & 1)
при этом если a==b, то BB == 0, иначе BB == 1.

Далее младший бит в BB ставим на все остальные позиции:
BBB = (BB & 1) | ((BB & 1) << 1) | ... | ((BB & 1) << (n-1))
получим число 1...1 (число из всех единиц), если a!=b, либо 0...0 (если a==b).
к полученному числу и y применяем &.

А далее,
rezult = AAA & x | BBB & y;

вместо A, AA, AAA, BB, BBB можно вставлять выражения (то есть не будет лишних переменных), но выражение будет ОГРОМНЫМ.
2
stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
18.07.2013, 14:09  [ТС] #19
Большое спасибо!
0
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,530
Завершенные тесты: 1
18.07.2013, 14:13 #20
Цитата Сообщение от Thinker Посмотреть сообщение
~(a^b)
Я тут все пытался тоже самое замутить, но через ~(~a & b)

По сути нам надо всего лишь построить на доступной логике общий алгоритм, превращающий любое число в ноль (или единицу).
1
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 14:24 #21
ну, 0 и 1 мы получим, а дальше? если имеется умножение, то все просто, иначе большие выражения всплывут, и то, если мы разрядность знаем.
1
SatanaXIII
Супер-модератор
Эксперт С++
5616 / 2651 / 246
Регистрация: 01.11.2011
Сообщений: 6,530
Завершенные тесты: 1
18.07.2013, 14:42 #22
Можно ли использовать циклы?

Я остановился на том, что нужно использовать выражение типа
(~(~a & v) & r1 )
которое даст нам result1, если a и value1 равны. В противном случае оно нам даст разницу меж всеми тремя. И как-то надо прикрутить к нему вторую часть, исключающую эту разницу и, при этом, добавляющую result2, если значения условия не равны.
Просто мысль. Сочинить запись я не смог.
1
stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
18.07.2013, 18:10  [ТС] #23
Нет циклов не должно быть! Вообще необходимо реализовать более быструю альтернативы условным операторам 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;
}
Еще раз большое спасибо за инфу!
0
Evg
Эксперт CАвтор FAQ
17944 / 6175 / 411
Регистрация: 30.03.2009
Сообщений: 16,952
Записей в блоге: 27
18.07.2013, 18:20 #24
Что-то мне кажется, что тут излишне сложные решения:

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 секунду
Ой я дятел.... условие невнимательно прочитал
1
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 18:50 #25
Цитата Сообщение от 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;
1
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,929
18.07.2013, 19:24 #26
вот решил для байта если размерность числа разная то без цикла не обойтись(по моему)
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);
а вот если бы привел к знаковому и загнал бы к старшему биту то не пришлось бы это писать
сдвиг вправо для знаковых и беззнаковых отличается
али забыл
2
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.07.2013, 19:30 #27
ValeryS, сдвиг отличается в одном случае:
сдвиг вправо отрицательного числа.
Только причем тут это? алгоритм работает для любых чисел (со знаком и без), все учтено
у нас в c либо 0, либо 1. нам либо 0...0 надо получить, либо 1...1.
1
ValeryS
Модератор
6653 / 5062 / 470
Регистрация: 14.02.2011
Сообщений: 16,929
18.07.2013, 19:35 #28
Цитата Сообщение от 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 Посмотреть сообщение
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;
результат один и тот же 0 или 0xFF
но у меня сдвиг во второй строчке проще
загоняем все биты в старший
в результате получаем или 0 или -128 (0x80)
потом разом сдвигаем на семь и получаем или 0 или -1(0xFF)
а в остальном параллельно думаем
2
Thinker
18.07.2013, 19:42     Битовые операции
  #29

Не по теме:

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

1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2013, 19:42
Привет! Вот еще темы с ответами:

Битовые операции - C++
Дано задание : Ввести последовательность из 8-ми символов. Если сумма единиц в представлении символа нечетная, то заменить 2 старших бита...

Битовые операции - C++
помогите написать программу в консоли... я вообще не знаю эту тему и не знаю ка делать... вот, задача.. Создайте программу,...

Битовые операции - C++
Задача. Я не понимаю что тут делать. Кто то что то понимает? Элементарное я понимаю сдвиги и прочее но это вообще:wall: Умоляю,...

Битовые операции - C++
Доброго времени суток! Есть задача: Даны два целых без знаковых числа. Остатки от деления их на 16 заносятся соответственно в 4 младших и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.07.2013, 19:42
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru