Найти следующее после 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;
        }
    }
}

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

@kazak · 22.08.2011, 15:38

Да, я уже понял по первым числам

@easybudda · 22.08.2011, 23:38

Логика та же, цикл немного по-другому сделал. Если следующего числа не получится, возвращается то же число, что можно отслеживать и сообщать в выводе, но мне лень было... Ну и двоичный вывод сделал для наглядности...

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
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <limits.h>
 
#define INT_BIT (CHAR_BIT * sizeof(int))
 
unsigned next(unsigned num){
    int i;
    
    for ( i = 0; i < INT_BIT - 1; ++i )
        if ( ( num & ( 1 << i ) ) && ( ! ( num & ( 1 << ( i + 1 ) ) ) ) )
            return ( ( num & ~ ( 1 << i ) ) | ( 1 << ( i + 1 ) ) );
    
    return num;
}
 
char * binstr(unsigned num){
    static char buf[INT_BIT + 1] = { 0 };
    char * pBuf = buf;
    int i = INT_BIT;
    
    while ( i-- )
        *pBuf++ = ( num & ( 1 << i ) ) ? '1' : '0';
    
    return buf;
}
 
int main(void){
    unsigned num;
    
    while ( printf("Number: ") && scanf("%u", &num) == 1 ){
        printf("%12u : %s\n", num, binstr(num));
        num = next(num);
        printf("%12u : %s\n", num, binstr(num));
    }
    
    return 0;
}

@x1Mike7x · 22.08.2011, 23:58

Нашёл у себя в когда-то нагуглиных алгоритмах

C++
1
2
3
4
5
6
7
8
9
10
11
unsigned next( unsigned X )  
{ 
    unsigned smallest, ripple, new_smallest, ones; 
    if ( X == 0 ) 
        return 0; 
    smallest = ( X & -X ); 
    ripple = X + smallest; 
    new_smallest = ( ripple & -ripple ); 
    ones = ( ( new_smallest / smallest ) >> 1 ) - 1; 
    return ripple | ones; 
}

@Olga_ · 23.08.2011, 10:17

Малость подумав, можно return упростить:

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

Новые блоги и статьи Все статьи Все блоги /
SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .	Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .

@kazak 3605 / 2745 / 356 Регистрация: 11.03.2009 Сообщений: 6,313
	22.08.2011, 15:38
	Да, я уже понял по первым числам 0

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

Решение