Найти следующее после n число, в двоичной записи которого столько же единиц

@diagon · Регистрация: 02.05.2010

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

Доброго времени суток.
Вопрос в названии темы, полное условие тут.
Перебор не проходит.
Пробовал

так

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
#include <iostream>
int ones_count(int n){
    int res = 0;
    for( ; n ; n >>= 1)
        res += n & 1;
    return res;
}
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    std::cin >> n;
    if ( !(n & (n - 1) ) ) //если степень двойки
    {
        std::cout << 1ll * n * 2;
        return 0;
    }
    int n_count = ones_count(n);
    for (;;)
    {
        ++n;
        if (ones_count(n) == n_count)
        {
            std::cout << n;
            return 0;
        }
    }
}

Что-то не могу дойти...
Если число - степень двойки, то ответом будет следующая за ним степень двойки. Больше никаких закономерностей не выявил...
Желательно решить с использованием только побитовых операций, т.е. без массивов, битсетов, логарифмов и прочей нечисти.

@Olga_ · 22.08.2011, 13:37

Diagon, думаю задача простая. Ищем самую правую цепочку 01 и ее заменяем на 10. Вот как.

Например, из 1010 получаем 1100, из 1011 - 1101

@grizlik78 · 22.08.2011, 13:39

Мне кажется, надо выделить самую правую единичку и перенести её на место ближайшего к ней ноля слева. Что-то вроде этого:
10110110
+
00000010
--------
10111100
or
10110110
--------
10111110
xor
00000010
--------
10111100
Но я мог ещё не проснуться

Добавлено через 1 минуту
Эх, опоздал чуток.

@Olga_ · 22.08.2011, 13:40

В посте 2 алгоритм

@diagon · 22.08.2011, 13:42 **[ТС]**

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

grizlik78, лучше ноль искать, проще будет.

Мне не надо проще, мне надо меньше символов =)
Спасибо, буду реализовывать...

@Olga_ · 22.08.2011, 13:44

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

Мне не надо проще, мне надо меньше символов =)
Спасибо, буду реализовывать...

Последний вариант, созревший в голове, в посте 2.

@grizlik78 · 22.08.2011, 13:46

Так. Получается, что я ещё не проснулся

Неправильно у меня.

@x1Mike7x · 22.08.2011, 13:47

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

10110110
+
00000010
--------
10111100
or
10110110
--------
10111110
xor
00000010
--------
10111100

Но мы же должны получить 10111001...

@Olga_ · 22.08.2011, 13:48

А это просто, выделяем по 2 бита и проверяем на равенство:
if (x & 3 == 1),
затем сдвигаем на 1 бит вправо

@diagon · 22.08.2011, 13:50 **[ТС]**

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

10111100

Это же 188 получается, а 185 поближе будет. Хм.
Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо.

@grizlik78 · 22.08.2011, 13:51

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

Но мы же должны получить 10111001...

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

Это же 188 получается, а 185 поближе будет. Хм.

Да я уже понял, что не прав. Пойду-ка подумаю спокойно

@Olga_ · 22.08.2011, 13:53

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

Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо.

Вы про чей вариант? Если мой, то ищем самую правую цепочку 01

@diagon · 22.08.2011, 13:56 **[ТС]**

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

А это просто, выделяем по 2 бита и проверяем на равенство:
if (x & 3 == 1),
затем сдвигаем на 1 бит вправо

Что-то я туплю... Сдвигаем направо что? x или 3?

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

Вы про чей вариант? Если мой, то ищем самую правую цепочку 01

Про ваш, опечатался, 01 имел в виду. Теперь вопрос, как ее там найти, я что-то не очень понял...
Вернее не как найти, а как изменить на 10.

@Olga_ · 22.08.2011, 14:13

Сдвигаем x, а число 3 здесь фигурирует как 0...011. Если хотите, алгоритм вам напишу

Добавлено через 3 минуты
Вот, функция возвращает требуемое число:

C++
1
2
3
4
5
6
7
8
9
10
unsigned long Search(unsigned long x)
{
   unsigned long y = x, i = 0;
   while (y & 3 != 1)
   {
      i++;
      y >>= 1;
   }
   return x ^ (3 << (i-1));
}

@Puporev · 22.08.2011, 14:15

Здесь еще нужно предусмотреть варианты типа
1000000
1111111

@diagon · 22.08.2011, 14:16 **[ТС]**

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

Вот, функция возвращает требуемое число:

Эх, практически то же самое написал, но с return ошибся...
Спасибо всем, кто откликнулся!

@Olga_ · 22.08.2011, 14:17

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

Здесь еще нужно предусмотреть варианты типа
1000000
1111111

По заданию такие варианты отпадают, 111, превращается в 1011

@diagon · 22.08.2011, 14:19 **[ТС]**

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

1000000

n *= 2;

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

1111111

Такое получиться, если следующее за ним число будет степенью двойки... Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.

@grizlik78 · 22.08.2011, 14:22

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

Вот, функция возвращает требуемое число:

а из такого что она выведет?
011110000

@Olga_ · 22.08.2011, 14:24

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

Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.

Diagon, 2^30 это 010...0 переходит в 10...0, как раз 32 бита

Добавлено через 38 секунд

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

а из такого что она выведет?
011110000

101110000

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 09.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 13:37
	Diagon, думаю задача простая. Ищем самую правую цепочку 01 и ее заменяем на 10. Вот как. Например, из 1010 получаем 1100, из 1011 - 1101 1

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	22.08.2011, 13:39
	Мне кажется, надо выделить самую правую единичку и перенести её на место ближайшего к ней ноля слева. Что-то вроде этого: 10110110 + 00000010 -------- 10111100 or 10110110 -------- 10111110 xor 00000010 -------- 10111100 Но я мог ещё не проснуться Добавлено через 1 минуту Эх, опоздал чуток. 1

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 13:40
	В посте 2 алгоритм 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	22.08.2011, 13:46
	Так. Получается, что я ещё не проснулся Неправильно у меня. 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 13:48
	А это просто, выделяем по 2 бита и проверяем на равенство: if (x & 3 == 1), затем сдвигаем на 1 бит вправо 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	22.08.2011, 14:15
	Здесь еще нужно предусмотреть варианты типа 1000000 1111111 1