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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 740
Записей в блоге: 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)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.09.2013, 18:23     Побитовые операции #21
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Возвращает 1, если X можно представить в виде N-бит
Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 740
Записей в блоге: 1
25.09.2013, 18:27  [ТС]     Побитовые операции #22
Цитата Сообщение от Qwertiy Посмотреть сообщение
Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?
К сожалению я аналогично не понимаю вообще)
Ладно спасибо и на том что есть уже.
Brain_Dead
 Аватар для Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 34
27.09.2013, 18:44     Побитовые операции #23
Насчёт каждого третьего бита.
Поскольку требуется возвращать слово с каждым третьим битом, то выглядеть это будет примерно так:
...001001001001, а всего 31 разряд. (не считая старший бит)

Тут, поскольку аргументов у функции нет, то различать значения 1 и 8 в выражениях thirdBits() & 1 и thirdBits() & 8 она никак не сможет.

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

Если вспомнить, что в восьмеричной системе счисления числа вида 1001001 выглядят как 111, то функция в итоге может выглядеть так:

C++
1
2
3
4
int thirdBits()
{
    return 01111111111;
}
Поскольку возвращаемое число больше 0, то можно использовать знаковый int.

(в записи восьмеричных чисел в начале ставится 0, если что)
Brain_Dead
 Аватар для Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 34
28.09.2013, 22:01     Побитовые операции #24
По поводу функции FitsBits.
Two's complement - это дополнительный код. Способ представления отрицательных чисел.
Статья о нём в википедии: http://ru.wikipedia.org/wiki/%D0%94%...81%D0%BB%D0%B0)

Судя по всему, нам необходимо определить, попадёт ли число x в диапазон: [- 2^n; 2^n - 1]

Решение выглядит примерно так:

C++
1
2
3
4
int FitsBits(int x, int n)
{
    return !(((~x & (x >> 31)) + (x & ~(x >> 31))) >> (n + ~0));
}
Про отрицательный ноль можно прочитать там же.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2013, 22:37     Побитовые операции
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
DmitryM5
Love~
 Аватар для DmitryM5
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 740
Записей в блоге: 1
29.09.2013, 22:37  [ТС]     Побитовые операции #25
Цитата Сообщение от Brain_Dead Посмотреть сообщение
По поводу функции FitsBits.
Two's complement - это дополнительный код. Способ представления отрицательных чисел.
Статья о нём в википедии: http://ru.wikipedia.org/wiki/%D0%94%...81%D0%BB%D0%B0)

Судя по всему, нам необходимо определить, попадёт ли число x в диапазон: [- 2^n; 2^n - 1]

Решение выглядит примерно так:

C++
1
2
3
4
int FitsBits(int x, int n)
{
    return !(((~x & (x >> 31)) + (x & ~(x >> 31))) >> (n + ~0));
}
Про отрицательный ноль можно прочитать там же.
Thanks!
Yandex
Объявления
29.09.2013, 22:37     Побитовые операции
Ответ Создать тему
Опции темы

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