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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

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

22.08.2011, 13:25. Просмотров 2541. Ответов 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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.08.2011, 13:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти следующее после n число, в двоичной записи которого столько же единиц (C++):

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

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

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

Определить элемент этого массива, в двоичной записи которого максимальное число единиц - C++
Задан массив целых чисел. Определить элемент этого массива, в двоичной записи которого максимальное число единиц. С помощью чего можно...

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

Среди всех n-битных двоичных чисел указать количество тех, в двоичной записи которых нет k единиц подряд - C++
Помогите пожалуйста понять в чём ошибка! Задание такое: среди всех n-битных двоичных чисел указать количество тех, у которых в двоичной...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:16  [ТС] #16
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
Эх, практически то же самое написал, но с return ошибся...
Спасибо всем, кто откликнулся!
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:17 #17
Цитата Сообщение от Puporev Посмотреть сообщение
Здесь еще нужно предусмотреть варианты типа
1000000
1111111
По заданию такие варианты отпадают, 111, превращается в 1011
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:19  [ТС] #18
Цитата Сообщение от Puporev Посмотреть сообщение
1000000
n *= 2;

Цитата Сообщение от Puporev Посмотреть сообщение
1111111
Такое получиться, если следующее за ним число будет степенью двойки... Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
22.08.2011, 14:22 #19
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
а из такого что она выведет?
011110000
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:24 #20
Цитата Сообщение от diagon Посмотреть сообщение
Правда что при этом делать затрудняюсь ответить... Хотя оно же само преобразуется в правильный вариант.
Diagon, 2^30 это 010...0 переходит в 10...0, как раз 32 бита

Добавлено через 38 секунд
Цитата Сообщение от grizlik78 Посмотреть сообщение
а из такого что она выведет?
011110000
101110000
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
22.08.2011, 14:26 #21
А должна бы 100000111
Но она вообще какое-то другое число выводит. Пытаюсь понять почему.
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:29  [ТС] #22
Цитата Сообщение от Olga_ Посмотреть сообщение
Вот, функция возвращает требуемое число:
Хм...
Почему-то возвращает меньшее значение, чем число...
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:32 #23
Сейчас подумаю

Добавлено через 1 минуту
Точно, надо искать 01, заменить на 10 и группу правых единиц сдвинуть вправо, спасибо, grizlik78. Сейчас сделаю
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
22.08.2011, 14:33 #24
в условии ( y & 3 != 1) не учитывается приоритет.
У & он ниже, чем у !=
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:36  [ТС] #25
Цитата Сообщение от grizlik78 Посмотреть сообщение
в условии ( y & 3 != 1) не учитывается приоритет.
У & он ниже, чем у !=
Не в нем дело, gcc ворнинг выдавал и я поставил там скобки.
0
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:36 #26
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
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
22.08.2011, 14:37 #27
Цитата Сообщение от diagon Посмотреть сообщение
Не в нем дело, gcc ворнинг выдавал и я поставил там скобки.
Ну так со скобками там не (i-1) должно быть, а просто i. Но функция всё-равно делает не то, что надо
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:40 #28
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
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:43 #29
Цитата Сообщение от 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_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:45 #30
не не, вот
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2011, 14:45
Привет! Вот еще темы с ответами:

Дано натуральное число m. Найти такое натуральное n, что двоичная запись n получается из двоичной записи m изменением порядка цифр на обратный ( - C++
Дано натуральное число m. Найти такое натуральное n, что двоичная запись n получается из двоичной записи m изменением порядка цифр на...

Перевести число из двоичной записи в десятичную - C++
Дана строка, изображающая двоичную запись целого положительного числа. Вывести строку, изображающую десятичную запись этого же числа....

Выведите четное число, следующее после заданного - C++
Следующее четное На вход дается натуральное число N. Выведите следующее за ним четное число Формат входных данных На вход...

В заданном массиве вывести следующее минимальное число после нуля - C++
Дан массив {0,0,0,0,0,77,522,230,0,56,59,35,0,57} Нужно вывести следующее минимальное число после 0


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.08.2011, 14:45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru