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

@DmitryM5 · Регистрация: 27.08.2013

Студворк — интернет-сервис помощи студентам

Помогите решить несколько задач по битовым операциям,они все малы по реализации.
И объяснить начиная с 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

@Qwertiy · 25.09.2013, 18:23

Сообщение от DmitryM5

Возвращает 1, если X можно представить в виде N-бит

Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?

@DmitryM5 · 25.09.2013, 18:27 **[ТС]**

Сообщение от Qwertiy

Что значит в виде n бит? 5 тремя нельзя, а -4 можно. Не понимаю. И при чём тут дополнительное число (two's complement integer)?

К сожалению я аналогично не понимаю вообще)
Ладно спасибо и на том что есть уже.

@Brain_Dead · 27.09.2013, 18:44

Насчёт каждого третьего бита.
Поскольку требуется возвращать слово с каждым третьим битом, то выглядеть это будет примерно так:
...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 · 28.09.2013, 22:01

По поводу функции FitsBits.
Two's complement - это дополнительный код. Способ представления отрицательных чисел.
Статья о нём в википедии: http://ru.wikipedia.org/wiki/%... 0%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));
}

Про отрицательный ноль можно прочитать там же.

@DmitryM5 · 29.09.2013, 22:37 **[ТС]**

Сообщение от Brain_Dead

По поводу функции FitsBits.
Two's complement - это дополнительный код. Способ представления отрицательных чисел.
Статья о нём в википедии: http://ru.wikipedia.org/wiki/%... 0%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!

Новые блоги и статьи Все статьи Все блоги /
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .