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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
24.09.2013, 22:55     Побитовые операции #1
Помогите решить несколько задач по битовым операциям,они все малы по реализации.
И объяснить начиная с 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
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,022
Записей в блоге: 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: << -
Даже нужно без цикла..
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
24.09.2013, 23:11  [ТС]     Побитовые операции #3
Пасиба,почему-то в дебаг версии не компилируется,а в релизе норм.
Миниатюры
Побитовые операции  
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
24.09.2013, 23:19  [ТС]     Побитовые операции #4
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Пасиба,почему-то в дебаг версии не компилируется,а в релизе норм.
Все,переделал проект нету этой ошибки.
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,022
Записей в блоге: 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-бинтых систем работает))
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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-бинтых систем работает))
И так нормально,спасибо!
ЭЭЭЭ последнее не понял
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,022
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:39     Побитовые операции #7
Цитата Сообщение от DmitryM5 Посмотреть сообщение
ЭЭЭЭ последнее не понял
Просто возвращается число в котором установлен каждый 3-й бит начиная с младшего) Мне сейчас некогда над этим думать..

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

Добавлено через 2 минуты
Да, и в функции fromNtoMBits у меня учитываются биты с n по m не включительно. Не знаю как именно они должны учитываться, в задании сказано не однозначно..
Не знаю,вроде учитываются m и n.(Assert проходит).
Как понять число в котором установлен каждый третий бит ?
Это типа ...00100100?так ведь можно до бесконечности??
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,022
Записей в блоге: 10
Завершенные тесты: 1
24.09.2013, 23:48     Побитовые операции #9
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Как понять число в котором установлен каждый третий бит ?
Это типа ...00100100?так ведь можно до бесконечности??
В int бесконечное число не поместится. В моем случае int 32 бита.
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
24.09.2013, 23:56  [ТС]     Побитовые операции #10
Блин,больше нету спецов по битам?
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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.
Brain_Dead
 Аватар для Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 34
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, работает.
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 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, работает.
Спасибо!Жду еще что нибудь
golatin
259 / 216 / 38
Регистрация: 12.10.2011
Сообщений: 311
Завершенные тесты: 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;
}
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
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?
castaway
Эксперт С++
4844 / 2983 / 367
Регистрация: 10.11.2010
Сообщений: 11,022
Записей в блоге: 10
Завершенные тесты: 1
25.09.2013, 13:39     Побитовые операции #16
Цитата Сообщение от Qwertiy Посмотреть сообщение
Что-то я не понял, а зачем там в аргументах x?
Функция возвращает биты с n по m из числа x.

Добавлено через 5 минут
Цитата Сообщение от Qwertiy Посмотреть сообщение
Не соответствует примеру... Там с какого-то перепуга биты в 1-индексации...
Да, поэтому я вижу только такое решение:
C++
1
2
3
int nthBit(int x, int n) {
    return ((x << 1) >> n) & 1;
}
Но в таком случае нельзя будет взять последний бит, т.к. при сдвиге влево на один он просто затрется...
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.09.2013, 13:53     Побитовые операции #17
Цитата Сообщение от castaway Посмотреть сообщение
Да, поэтому я вижу только такое решение:
Сдвига влево нет в разрешённых операциях
Возможно просто опечатка в задании, т. к. это бред, считать так биты...

Добавлено через 8 минут
Цитата Сообщение от DmitryM5 Посмотреть сообщение
int sign(int x) {
C++
1
return return (x>>/*BEGIN:constant*/((sizeof(int)<<3)-1)/*END*/)|!!x;
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
25.09.2013, 16:51  [ТС]     Побитовые операции #18
Спасибо всем большое!
Если кто-то поможет с этим,буду счастлив!
C++
1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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
}
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.09.2013, 17:21     Побитовые операции #19
Цитата Сообщение от DmitryM5 Посмотреть сообщение
int fitsBits(int x, int n) {
Не понимаю описание. Поясни, что оно должно делать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2013, 17:48     Побитовые операции
Еще ссылки по теме:

C++ Найти все целые числа из диапазона
C++ Ввести число и вывести результат циклического сдвига его битов на 1 разряд влево
C++ В каждом числе массива определить количество разрядов, равных "1"

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

Или воспользуйтесь поиском по форуму:
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 743
Записей в блоге: 1
25.09.2013, 17:48  [ТС]     Побитовые операции #20
Цитата Сообщение от Qwertiy Посмотреть сообщение
Не понимаю описание. Поясни, что оно должно делать.
Возвращает 1, если X можно представить в виде N-бит
не знаю к сожалению
Yandex
Объявления
25.09.2013, 17:48     Побитовые операции
Ответ Создать тему
Опции темы

Текущее время: 21:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru