Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 13:25     Найти следующее после n число, в двоичной записи которого столько же единиц #1
Доброго времени суток.
Вопрос в названии темы, полное условие тут.
Перебор не проходит.
Пробовал
так
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;
        }
    }
}

Что-то не могу дойти...
Если число - степень двойки, то ответом будет следующая за ним степень двойки. Больше никаких закономерностей не выявил...
Желательно решить с использованием только побитовых операций, т.е. без массивов, битсетов, логарифмов и прочей нечисти.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.08.2011, 13:25     Найти следующее после n число, в двоичной записи которого столько же единиц
Посмотрите здесь:

C++ Найти число в двоичной записи которого максимальное число единиц
C++ Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц.
C++ Дано натуральное число m. Найти такое натуральное n, что двоичная запись n получается из двоичной записи m изменением порядка цифр на обратный (
C++ Среди простых чисел, не превосходящих N, найти такое, в десятичной записи которого максимальное число единиц
C++ Определить элемент этого массива, в двоичной записи которого максимальное число единиц
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 13:37     Найти следующее после n число, в двоичной записи которого столько же единиц #2
Diagon, думаю задача простая. Ищем самую правую цепочку 01 и ее заменяем на 10. Вот как.

Например, из 1010 получаем 1100, из 1011 - 1101
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
22.08.2011, 13:39     Найти следующее после n число, в двоичной записи которого столько же единиц #3
Мне кажется, надо выделить самую правую единичку и перенести её на место ближайшего к ней ноля слева. Что-то вроде этого:
10110110
+
00000010
--------
10111100
or
10110110
--------
10111110
xor
00000010
--------
10111100

Но я мог ещё не проснуться

Добавлено через 1 минуту
Эх, опоздал чуток.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 13:40     Найти следующее после n число, в двоичной записи которого столько же единиц #4
В посте 2 алгоритм
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 13:42  [ТС]     Найти следующее после n число, в двоичной записи которого столько же единиц #5
Цитата Сообщение от Olga_ Посмотреть сообщение
grizlik78, лучше ноль искать, проще будет.
Мне не надо проще, мне надо меньше символов =)
Спасибо, буду реализовывать...
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 13:44     Найти следующее после n число, в двоичной записи которого столько же единиц #6
Цитата Сообщение от diagon Посмотреть сообщение
Мне не надо проще, мне надо меньше символов =)
Спасибо, буду реализовывать...
Последний вариант, созревший в голове, в посте 2.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
22.08.2011, 13:46     Найти следующее после n число, в двоичной записи которого столько же единиц #7
Так. Получается, что я ещё не проснулся Неправильно у меня.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
22.08.2011, 13:47     Найти следующее после n число, в двоичной записи которого столько же единиц #8
Цитата Сообщение от grizlik78 Посмотреть сообщение
10110110
+
00000010
--------
10111100
or
10110110
--------
10111110
xor
00000010
--------
10111100
Но мы же должны получить 10111001...
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 13:48     Найти следующее после n число, в двоичной записи которого столько же единиц #9
А это просто, выделяем по 2 бита и проверяем на равенство:
if (x & 3 == 1),
затем сдвигаем на 1 бит вправо
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 13:50  [ТС]     Найти следующее после n число, в двоичной записи которого столько же единиц #10
Цитата Сообщение от grizlik78 Посмотреть сообщение
10111100
Это же 188 получается, а 185 поближе будет. Хм.
Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
22.08.2011, 13:51     Найти следующее после n число, в двоичной записи которого столько же единиц #11
Цитата Сообщение от x1Mike7x Посмотреть сообщение
Но мы же должны получить 10111001...
Цитата Сообщение от diagon Посмотреть сообщение
Это же 188 получается, а 185 поближе будет. Хм.
Да я уже понял, что не прав. Пойду-ка подумаю спокойно
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 13:53     Найти следующее после n число, в двоичной записи которого столько же единиц #12
Цитата Сообщение от diagon Посмотреть сообщение
Что бы найти в битовом представлении 10, придется сначала перегнать числу в строку, затем обратно... Длинновато получиться. Но вариант интересный, спасибо.
Вы про чей вариант? Если мой, то ищем самую правую цепочку 01
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 13:56  [ТС]     Найти следующее после n число, в двоичной записи которого столько же единиц #13
Цитата Сообщение от Olga_ Посмотреть сообщение
А это просто, выделяем по 2 бита и проверяем на равенство:
if (x & 3 == 1),
затем сдвигаем на 1 бит вправо
Что-то я туплю... Сдвигаем направо что? x или 3?

Цитата Сообщение от Olga_ Посмотреть сообщение
Вы про чей вариант? Если мой, то ищем самую правую цепочку 01
Про ваш, опечатался, 01 имел в виду. Теперь вопрос, как ее там найти, я что-то не очень понял...
Вернее не как найти, а как изменить на 10.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:13     Найти следующее после n число, в двоичной записи которого столько же единиц #14
Сдвигаем 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
Модератор
 Аватар для Puporev
50412 / 38343 / 12293
Регистрация: 18.05.2008
Сообщений: 86,831
22.08.2011, 14:15     Найти следующее после n число, в двоичной записи которого столько же единиц #15
Здесь еще нужно предусмотреть варианты типа
1000000
1111111
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:16  [ТС]     Найти следующее после n число, в двоичной записи которого столько же единиц #16
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
Эх, практически то же самое написал, но с return ошибся...
Спасибо всем, кто откликнулся!
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:17     Найти следующее после n число, в двоичной записи которого столько же единиц #17
Цитата Сообщение от Puporev Посмотреть сообщение
Здесь еще нужно предусмотреть варианты типа
1000000
1111111
По заданию такие варианты отпадают, 111, превращается в 1011
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:19  [ТС]     Найти следующее после n число, в двоичной записи которого столько же единиц #18
Цитата Сообщение от Puporev Посмотреть сообщение
1000000
n *= 2;

Цитата Сообщение от Puporev Посмотреть сообщение
1111111
Такое получиться, если следующее за ним число будет степенью двойки... Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
22.08.2011, 14:22     Найти следующее после n число, в двоичной записи которого столько же единиц #19
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
а из такого что она выведет?
011110000
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2011, 14:24     Найти следующее после n число, в двоичной записи которого столько же единиц
Еще ссылки по теме:

Среди всех n-битных двоичных чисел указать количество тех, в двоичной записи которых нет k единиц подряд C++
Перевести число из двоичной записи в десятичную C++
C++ Visual Studio. Определить элемент этого массива, в двоичной записи которого максимальное число единиц C++

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:24     Найти следующее после n число, в двоичной записи которого столько же единиц #20
Цитата Сообщение от diagon Посмотреть сообщение
Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.
Diagon, 2^30 это 010...0 переходит в 10...0, как раз 32 бита

Добавлено через 38 секунд
Цитата Сообщение от grizlik78 Посмотреть сообщение
а из такого что она выведет?
011110000
101110000
Yandex
Объявления
22.08.2011, 14:24     Найти следующее после n число, в двоичной записи которого столько же единиц
Ответ Создать тему
Опции темы

Текущее время: 14:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru