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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
#1

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

24.09.2013, 22:55. Просмотров 2397. Ответов 24
Метки нет (Все метки)

Помогите решить несколько задач по битовым операциям,они все малы по реализации.
И объяснить начиная с 3 задачи,что нужно сделать?А то не совсем понятно.
Help please!
Задания:
1.Сделал,вроде правильно.
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Hint: recall De Morgan's laws
 */
int bitAnd(int x, int y) {
    return ~(~x|~y);   // TODO: your implementation goes here
}
2.Сделал.
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * nthBit - return n-th bit in x
 *   Example: bitAnd(4, 1) = 0, bitAnd(4, 3) = 1
 *   Legal ops: >> &
 *   Max ops: 4
 */
int nthBit(int x, int n) {
    return (x>>n) &1;
    // TODO: your implementation goes here
}
3.
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * setFirstNBits - returns a number with first (least significant) bits n set
 *   Example: setFirstNBits(3) = 7, setFirstNBits(0) = 0
 *   Legal ops: << -
 *   Max ops: 4
 *   Hint: 2^n - 1
 */
int setFirstNBits(int n) {
    // TODO: your implementation goes here
}
4.
C++
1
2
3
4
5
6
7
8
9
/* 
 * fromNtoMBits - returns a number composed from bits n to m
 *   Example: fromNtoMBits(4, 3, 5) = 1, fromNtoMBits(12, 3, 5) = 3
 *   Legal ops: >> & - setFirstNBits
 *   Max ops: 4
 */
int fromNtoMBits(int x, int n, int m) {
    // TODO: your implementation goes here
}
5.
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * thirdBits - return word with every third bit (starting from the least 
                significant bit, LSB) set to 1 and the rest set to 0
 *   thirdBits() & 1 == 1, thirdBits() & 8 == 8, etc.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 */
int thirdBits(void) {
    // TODO: your implementation goes here
}
Добавлено через 17 минут
Во 2 задании опечатка в Example: nthBit(4, 1) = 0, nthBit(4, 3) = 1
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2013, 22:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Побитовые операции (C++):

Побитовые операции - C++
От друга услышал идею о побитовой сортировки имен (например). К примеру, если у нас набор структурных переменных с анкетами работников, и...

Побитовые операции - C++
1-программа #include &lt;stdio.h&gt; #include &lt;windows.h&gt; int main(void) { char g; /* ??? ????????? */ char s; /* ??????? ?????? */ ...

Побитовые операции - C++
Пожалуйста, объясните как работают побитовые операторы &amp; и |. Например идет: i=03; j=01; k=i &amp; j; // k=1 k=i | j; // k=3 А почему...

Побитовые операции - C++
Задание: Дано целое неотрицательное число. Определить количество составляющих его шестнадцатеричных цифр, содержащих в двоичном...

Побитовые операции - C++
Всем доброго утра. Дана такая задача: есть два чсила,поменять местами 2 последние цифры этих чисел между собой, т.е. 2 последних Х заменить...

Побитовые операции - C++
Помогите, не могу понять как сделать эту программу( unsigned ChangeGroupBits(unsigned x, unsigned y, int n1, int n2); ChangeGroupBits–...

24
castaway
Эксперт С++
4919 / 3027 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:07 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от DmitryM5 Посмотреть сообщение
И объяснить начиная с 3 задачи,что нужно сделать?А то не совсем понятно.
Функция которая устанавливает первые n бит. 3 первых бита - это значение 7

Добавлено через 2 минуты
3.
C++
1
2
3
4
5
6
7
int setFirstNBits( int n ) {
    int r = 0;
    while ( n-- ) {
        r = (r << 1) | 1;
    }
    return r;
}
Добавлено через 2 минуты
Хотя можно и без цикла..
C++
1
2
3
int setFirstNBits( int n ) {
    return (1 << n) - 1;
}
Добавлено через 2 минуты
Legal ops: << -
Даже нужно без цикла..
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
24.09.2013, 23:11  [ТС] #3
Пасиба,почему-то в дебаг версии не компилируется,а в релизе норм.
0
Миниатюры
Побитовые операции  
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
24.09.2013, 23:19  [ТС] #4
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Пасиба,почему-то в дебаг версии не компилируется,а в релизе норм.
Все,переделал проект нету этой ошибки.
0
castaway
Эксперт С++
4919 / 3027 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:29 #5
Что-то я не соображу.. как можно сделать проще в голову не приходит, но если считать функцию setFirstNBits за операцию, тогда превышение операций..
C++
1
2
3
4
5
6
7
8
9
/* 
 * fromNtoMBits - returns a number composed from bits n to m
 *   Example: fromNtoMBits(4, 3, 5) = 1, fromNtoMBits(12, 3, 5) = 3
 *   Legal ops: >> & - setFirstNBits
 *   Max ops: 4
 */
int fromNtoMBits( int x, int n, int m ) {
    return (x >> (n - 1)) & setFirstNBits( m - n );
}
Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * thirdBits - return word with every third bit (starting from the least 
                significant bit, LSB) set to 1 and the rest set to 0
 *   thirdBits() & 1 == 1, thirdBits() & 8 == 8, etc.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 */
int thirdBits() {
    return 0x49249249;
}
Так конечно на вряд ли можно, но для 32-бинтых систем работает))
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
24.09.2013, 23:30  [ТС] #6
Цитата Сообщение от castaway Посмотреть сообщение
Что-то я не соображу.. как можно сделать проще в голову не приходит, но если считать функцию setFirstNBits за операцию, тогда превышение операций..
C++
1
2
3
4
5
6
7
8
9
/* 
 * fromNtoMBits - returns a number composed from bits n to m
 *   Example: fromNtoMBits(4, 3, 5) = 1, fromNtoMBits(12, 3, 5) = 3
 *   Legal ops: >> & - setFirstNBits
 *   Max ops: 4
 */
int fromNtoMBits( int x, int n, int m ) {
    return (x >> (n - 1)) & setFirstNBits( m - n );
}
Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
/* 
 * thirdBits - return word with every third bit (starting from the least 
                significant bit, LSB) set to 1 and the rest set to 0
 *   thirdBits() & 1 == 1, thirdBits() & 8 == 8, etc.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 */
int thirdBits() {
    return 0x49249249;
}
Так конечно на вряд ли можно, но для 32-бинтых систем работает))
И так нормально,спасибо!
ЭЭЭЭ последнее не понял
0
castaway
Эксперт С++
4919 / 3027 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:39 #7
Цитата Сообщение от DmitryM5 Посмотреть сообщение
ЭЭЭЭ последнее не понял
Просто возвращается число в котором установлен каждый 3-й бит начиная с младшего) Мне сейчас некогда над этим думать..

Добавлено через 2 минуты
Да, и в функции fromNtoMBits у меня учитываются биты с n по m не включительно. Не знаю как именно они должны учитываться, в задании сказано не однозначно..
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
24.09.2013, 23:45  [ТС] #8
Цитата Сообщение от castaway Посмотреть сообщение
Просто возвращается число в котором установлен каждый 3-й бит начиная с младшего) Мне сейчас некогда над этим думать..

Добавлено через 2 минуты
Да, и в функции fromNtoMBits у меня учитываются биты с n по m не включительно. Не знаю как именно они должны учитываться, в задании сказано не однозначно..
Не знаю,вроде учитываются m и n.(Assert проходит).
Как понять число в котором установлен каждый третий бит ?
Это типа ...00100100?так ведь можно до бесконечности??
0
castaway
Эксперт С++
4919 / 3027 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:48 #9
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Как понять число в котором установлен каждый третий бит ?
Это типа ...00100100?так ведь можно до бесконечности??
В int бесконечное число не поместится. В моем случае int 32 бита.
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
24.09.2013, 23:56  [ТС] #10
Блин,больше нету спецов по битам?
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
25.09.2013, 08:33  [ТС] #11
Если все таки найдется добрый человек,дайте знать.
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
/* 
 * thirdBits - return word with every third bit (starting from the least 
                significant bit, LSB) set to 1 and the rest set to 0
 *   thirdBits() & 1 == 1, thirdBits() & 8 == 8, etc.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 */
int thirdBits(void) {
    // TODO: your implementation goes here
}
 
 
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 10
 *   Hint: compare the result of (0 xor 1) with (~0 & 1), then (0 & ~1). 
            The idea is already emerged here. Just test it over other 
            combinations ((1 xor 0), (0 xor 0), etc.).
 */
int bitXor(int x, int y) {
    // TODO: your implementation goes here
}
 
/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 */
int fitsBits(int x, int n) {
    // TODO: your implementation goes here
}
 
/* 
 * sign - return 1 if positive, 0 if zero, and -1 if negative
 *  Examples: sign(130) = 1
 *            sign(-23) = -1
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 10
 */
int sign(int x) {
    // TODO: your implementation goes here
}
/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 */
int getByte(int x, int n) {
    // TODO: your implementation goes here
}
Добавлено через 8 часов 16 минут
up.
0
Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 35
25.09.2013, 10:39 #12
По поводу "взаимоисключающего ИЛИ" (№4) - bitXor

Оговорка 1. Лучше не использовать знаковые типы. Поскольку у них старший бит отводится под знак, и разобрать, как работает ~, очень сложно.

Оговорка 2. Приоритет операции ~ выше, чем &.

C++
1
2
3
4
unsigned int bitXor(unsigned int x, unsigned int y)
{
    return ~(~(x&~y) & ~(~x&y));
}
И дополнительно.
1. Меньше, чем за 8 операций, сделать нельзя (базис).
2. Делал в Windows 7 64, работает.
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 886
Записей в блоге: 1
25.09.2013, 10:53  [ТС] #13
Цитата Сообщение от Brain_Dead Посмотреть сообщение
По поводу "взаимоисключающего ИЛИ" (№4) - bitXor

Оговорка 1. Лучше не использовать знаковые типы. Поскольку у них старший бит отводится под знак, и разобрать, как работает ~, очень сложно.

Оговорка 2. Приоритет операции ~ выше, чем &.

C++
1
2
3
4
unsigned int bitXor(unsigned int x, unsigned int y)
{
    return ~(~(x&~y) & ~(~x&y));
}
И дополнительно.
1. Меньше, чем за 8 операций, сделать нельзя (базис).
2. Делал в Windows 7 64, работает.
Спасибо!Жду еще что нибудь
0
golatin
269 / 226 / 44
Регистрация: 12.10.2011
Сообщений: 345
Завершенные тесты: 1
25.09.2013, 12:31 #14
C
1
2
3
4
int getByte(int x, int n) {
    // TODO: your implementation goes here
   return (x>>(n<<3))&0xFF;
}
1
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
25.09.2013, 13:08 #15
Цитата Сообщение от DmitryM5 Посмотреть сообщение
2. return (x>>n) &1;
Не соответствует примеру... Там с какого-то перепуга биты в 1-индексации...

Цитата Сообщение от DmitryM5 Посмотреть сообщение
4. fromNtoMBits - returns a number composed from bits n to m
Что-то я не понял, а зачем там в аргументах x?
1
25.09.2013, 13:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2013, 13:08
Привет! Вот еще темы с ответами:

Побитовые операции на с++ (<< и >>) - C++
Подскажите пожалуйста, такая задача - побитовый сдвиг на заданное количество символов сдвигает только цифры, как сделать чтобы он то же...

Побитовые операции - C++
Здравствуйте уважаемые читатели форума! СОвсем не представляю как сделать простейшую програмку на С++. Нужно вычислить номер позиции...

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

Побитовые операции - C++
Задача: битовый образ 8*8 задается при помощи 8 байт, каждый байт состоит, соответственно, из 8 бит, бит={0,1}; при помощи побитовых...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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