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

@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!

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .