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

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

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

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

24.09.2013, 22:55. Просмотров 2426. Ответов 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
Эксперт С++
4920 / 3028 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 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;
}
Но в таком случае нельзя будет взять последний бит, т.к. при сдвиге влево на один он просто затрется...
1
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
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;
2
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 892
Записей в блоге: 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
}
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
25.09.2013, 17:21 #19
Цитата Сообщение от DmitryM5 Посмотреть сообщение
int fitsBits(int x, int n) {
Не понимаю описание. Поясни, что оно должно делать.
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 892
Записей в блоге: 1
25.09.2013, 17:48  [ТС] #20
Цитата Сообщение от Qwertiy Посмотреть сообщение
Не понимаю описание. Поясни, что оно должно делать.
Возвращает 1, если X можно представить в виде N-бит
не знаю к сожалению
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
25.09.2013, 18:23 #21
Цитата Сообщение от DmitryM5 Посмотреть сообщение
Возвращает 1, если X можно представить в виде N-бит
Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?
1
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 892
Записей в блоге: 1
25.09.2013, 18:27  [ТС] #22
Цитата Сообщение от Qwertiy Посмотреть сообщение
Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?
К сожалению я аналогично не понимаю вообще)
Ладно спасибо и на том что есть уже.
0
Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 35
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, если что)
0
Brain_Dead
9 / 8 / 2
Регистрация: 25.09.2013
Сообщений: 35
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));
}
Про отрицательный ноль можно прочитать там же.
0
DmitryM5
Love~
51 / 51 / 3
Регистрация: 27.08.2013
Сообщений: 892
Записей в блоге: 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!
0
29.09.2013, 22:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2013, 22:37
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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