Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.59/29: Рейтинг темы: голосов - 29, средняя оценка - 4.59
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2

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

22.08.2011, 13:25. Показов 7100. Ответов 43
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток.
Вопрос в названии темы, полное условие тут.
Перебор не проходит.
Пробовал
так
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;
        }
    }
}

Что-то не могу дойти...
Если число - степень двойки, то ответом будет следующая за ним степень двойки. Больше никаких закономерностей не выявил...
Желательно решить с использованием только побитовых операций, т.е. без массивов, битсетов, логарифмов и прочей нечисти.
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
22.08.2011, 13:25
Ответы с готовыми решениями:

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

Найти число в двоичной записи которого максимальное число единиц
Среди простых чисел ,не превосходящих N ,найти такое ,в двоичной записи которого максимальное число единиц. Уважаемые форумчане помогите...

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

43
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
22.08.2011, 14:26
Студворк — интернет-сервис помощи студентам
А должна бы 100000111
Но она вообще какое-то другое число выводит. Пытаюсь понять почему.
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:29  [ТС]
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
Хм...
Почему-то возвращает меньшее значение, чем число...
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 14:32
Сейчас подумаю

Добавлено через 1 минуту
Точно, надо искать 01, заменить на 10 и группу правых единиц сдвинуть вправо, спасибо, grizlik78. Сейчас сделаю
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
22.08.2011, 14:33
в условии ( y & 3 != 1) не учитывается приоритет.
У & он ниже, чем у !=
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:36  [ТС]
Цитата Сообщение от grizlik78 Посмотреть сообщение
в условии ( y & 3 != 1) не учитывается приоритет.
У & он ниже, чем у !=
Не в нем дело, gcc ворнинг выдавал и я поставил там скобки.
0
204 / 205 / 16
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:36
C
1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned int next(unsigned int _in) {
 
    unsigned int out = _in;
    unsigned int i;
 
    for(i=0; i<30; i++) {
        if(((_in >> i) & 3) == 1) {
            out = (_in & ~(1 << i) | (2 << i));
            break;
        }
    }
    return out;
}
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
22.08.2011, 14:37
Цитата Сообщение от diagon Посмотреть сообщение
Не в нем дело, gcc ворнинг выдавал и я поставил там скобки.
Ну так со скобками там не (i-1) должно быть, а просто i. Но функция всё-равно делает не то, что надо
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 14:40
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 >> i) ^ 3) << i) | ((1 << (i - 1)) - 1);
}
0
204 / 205 / 16
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:43
Цитата Сообщение от Olga_ Посмотреть сообщение
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 >> i) ^ 3) << i) | ((1 << (i - 1)) - 1);
}
8 -> 19
7 -> 9

fail
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 14:45
не не, вот
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  i ? (((x >> i) ^ 3) << i) | ((1 << (i - 1)) - 1) : x ^ 3;
}
Ай нет, да что такое, спокойно подумаю
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:47  [ТС]
Я, видимо, чего-то не понимаю...
Но ответом на 182 должен быть 185.
Мое решение в лоб
C++
1
2
3
4
5
6
7
8
9
10
11
12
int f(int n){
    std::string bin = std::bitset<15> (n).to_string();
    for (int i = bin.size() - 1; i > 0; --i)
    {
        if (bin[i] == '1' && bin[i - 1] == '0')
        {
            std::swap(bin[i], bin[i-1]);
            break;
        }
    }
    return strtol(bin.c_str(), 0, 2);
}
А также функция villu выдают 186. Функция Ольги вообще что-то левое выдает >_> Дело в алгоритме, видимо...
Т.е. не все так просто. Все должно быть еще проще =\ Лучшие попытки - 114 символов.
0
204 / 205 / 16
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:50
а, ну да, косяк есть такой.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:56  [ТС]
Можно оставить перебор, но он будет загибаться на числах, которые являются степенью двойки - 1(т.е. в двоичной системе состоят только из единиц). Не могу понять, что на них выводить нужно.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 14:57
Вроде верно все
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  j ? (((x >> i) | 2) << i) | ((1 << (j - 1)) - 1) : x ^ (3 << i);
}
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:59  [ТС]
Цитата Сообщение от Olga_ Посмотреть сообщение
Вроде верно все
182 -> 188
3 -> 6
Дело в алгоритме, я выше безошибочную реализацию с STL привел.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 15:10
Все:
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  j ? (((x >> i) ^ 3) << i) | ((1 << j) - 1) : x ^ (3 << i);
}
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 15:14  [ТС]
Цитата Сообщение от Olga_ Посмотреть сообщение
Все:
Accepted =)
А можно краткое описание алгоритма? Просто обмен 01 на 10 я уже реализовывал, там результат немного другой получается.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
22.08.2011, 15:21
Цитата Сообщение от diagon Посмотреть сообщение
Accepted =)
А можно краткое описание алгоритма? Просто обмен 01 на 10 я уже реализовывал, там результат немного другой получается.
Сначала ищем самую правую последовательность 01 и попутно считаем количество единиц, стоящих после 01. Понятно, что эти единицы следуют сразу за 01, например 1011100. Здесь ровно 2 единицы после 01. Единиц после 01 может и не быть, например 0100. Переменная j отвечает за количество этих единиц. Если j>0, то надо заменить 01 на 10 а эти j единиц переместить в конец:
C++
1
(((x >> i) ^ 3) << i) | ((1 << j) - 1)
А если j=0, то просто заменяем 01 на 10:
C++
1
x ^ (3 << i)
1
 Аватар для kazak
3606 / 2746 / 356
Регистрация: 11.03.2009
Сообщений: 6,318
22.08.2011, 15:32
Чет взбрело в голову,
C++
1
2
3
4
5
6
7
unsigned int foo(unsigned int number)
{
   if (number & 1)
      return number + 2;
   else
   return number + 3;
}
,
на бумаге прикинул, вроде должно считать правильно.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 15:35  [ТС]
Цитата Сообщение от kazak Посмотреть сообщение
Чет взбрело в голову
Для степеней двойки надо умножать на 2. Это как минимум... Если (n + 1) - степень двойки, то надо еще что-то выводить. Может, еще частные случаи есть. А, и еще для единицы ответ 2 будет.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
22.08.2011, 15:35

Среди простых чисел найти найти такое, в двоичной записи которого максимальное число единиц.
Помогите пожалуйста! Среди простых чисел, не превосходящих n, найти такое, в двоичной записи которого максимальное число единиц.

Среди простых чисел найти такое, в двоичной записи которого максимальное число единиц
Среди простых чисел, не превосходящих заданного N, найти такое, в двоичной записи которого максимальное число единиц. Часть кода уже...

Среди простых чисел, не превосходящих N, найти такое, в двоичной записи которого максимальное число единиц
Среди простых чисел, не превосходящих N, найти такое, в двоичной записи которого максимальное число единиц.

Вывести десятичное простое число, в двоичной записи которого наибольшее число единиц
Привет всем! Помогите, пожалуйста. Суть задачи: На вход с клавиатуры программа получает N На выход выдает простое десятичное число,...

Определить элемент массива, в двоичной записи которого максимальное число единиц
Здравствуйте, помогите пожалуйста!:scratch: Задан массив целых чисел. Определить элемент этого массива, в двоичной записи которого...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru