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

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

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

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

так

C++

#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++

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

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 13:53	12
	Сообщение от diagon Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо. Вы про чей вариант? Если мой, то ищем самую правую цепочку 01 0

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

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

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

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.08.2011, 13:42 [ТС]	5
	Сообщение от Olga_ grizlik78, лучше ноль искать, проще будет. Мне не надо проще, мне надо меньше символов =) Спасибо, буду реализовывать... 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 13:44	6
	Сообщение от diagon Мне не надо проще, мне надо меньше символов =) Спасибо, буду реализовывать... Последний вариант, созревший в голове, в посте 2. 1

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

@x1Mike7x 222 / 135 / 19 Регистрация: 06.11.2010 Сообщений: 234
	22.08.2011, 13:47	8
	Сообщение от grizlik78 10110110 + 00000010 -------- 10111100 or 10110110 -------- 10111110 xor 00000010 -------- 10111100 Но мы же должны получить 10111001... 0

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

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.08.2011, 13:50 [ТС]	10
	Сообщение от grizlik78 10111100 Это же 188 получается, а 185 поближе будет. Хм. Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	22.08.2011, 13:51	11
	Сообщение от x1Mike7x Но мы же должны получить 10111001... Сообщение от diagon Это же 188 получается, а 185 поближе будет. Хм. Да я уже понял, что не прав. Пойду-ка подумаю спокойно 0

	22.08.2011, 14:24

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.08.2011, 13:56 [ТС]	13
	Сообщение от Olga_ А это просто, выделяем по 2 бита и проверяем на равенство: if (x & 3 == 1), затем сдвигаем на 1 бит вправо Что-то я туплю... Сдвигаем направо что? x или 3? Сообщение от Olga_ Вы про чей вариант? Если мой, то ищем самую правую цепочку 01 Про ваш, опечатался, 01 имел в виду. Теперь вопрос, как ее там найти, я что-то не очень понял... Вернее не как найти, а как изменить на 10. 0

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

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.08.2011, 14:16 [ТС]	16
	Сообщение от Olga_ Вот, функция возвращает требуемое число: Эх, практически то же самое написал, но с return ошибся... Спасибо всем, кто откликнулся! 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 14:17	17
	Сообщение от Puporev Здесь еще нужно предусмотреть варианты типа 1000000 1111111 По заданию такие варианты отпадают, 111, превращается в 1011 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	22.08.2011, 14:19 [ТС]	18
	Сообщение от Puporev 1000000 n = 2; Сообщение от Puporev* 1111111 Такое получиться, если следующее за ним число будет степенью двойки... Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	22.08.2011, 14:22	19
	Сообщение от Olga_ Вот, функция возвращает требуемое число: а из такого что она выведет? 011110000 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	22.08.2011, 14:24	20
	Сообщение от diagon Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант. Diagon, 2^30 это 010...0 переходит в 10...0, как раз 32 бита Добавлено через 38 секунд Сообщение от grizlik78 а из такого что она выведет? 011110000 101110000 0