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

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

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

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

22.08.2011, 13:25. Просмотров 2595. Ответов 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-битных двоичных чисел указать количество тех, у которых в двоичной...

43
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:47  [ТС] #31
Я, видимо, чего-то не понимаю...
Но ответом на 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
villu
203 / 204 / 4
Регистрация: 06.08.2011
Сообщений: 600
Записей в блоге: 1
22.08.2011, 14:50 #32
а, ну да, косяк есть такой.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:56  [ТС] #33
Можно оставить перебор, но он будет загибаться на числах, которые являются степенью двойки - 1(т.е. в двоичной системе состоят только из единиц). Не могу понять, что на них выводить нужно.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 14:57 #34
Вроде верно все
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
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 14:59  [ТС] #35
Цитата Сообщение от Olga_ Посмотреть сообщение
Вроде верно все
182 -> 188
3 -> 6
Дело в алгоритме, я выше безошибочную реализацию с STL привел.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 15:10 #36
Все:
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
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 15:14  [ТС] #37
Цитата Сообщение от Olga_ Посмотреть сообщение
Все:
Accepted =)
А можно краткое описание алгоритма? Просто обмен 01 на 10 я уже реализовывал, там результат немного другой получается.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
22.08.2011, 15:21 #38
Цитата Сообщение от 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
3050 / 2371 / 160
Регистрация: 11.03.2009
Сообщений: 5,436
Завершенные тесты: 1
22.08.2011, 15:32 #39
Чет взбрело в голову,
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
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.08.2011, 15:35  [ТС] #40
Цитата Сообщение от kazak Посмотреть сообщение
Чет взбрело в голову
Для степеней двойки надо умножать на 2. Это как минимум... Если (n + 1) - степень двойки, то надо еще что-то выводить. Может, еще частные случаи есть. А, и еще для единицы ответ 2 будет.
0
kazak
3050 / 2371 / 160
Регистрация: 11.03.2009
Сообщений: 5,436
Завершенные тесты: 1
22.08.2011, 15:38 #41
Да, я уже понял по первым числам
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
22.08.2011, 23:38 #42
Логика та же, цикл немного по-другому сделал. Если следующего числа не получится, возвращается то же число, что можно отслеживать и сообщать в выводе, но мне лень было... Ну и двоичный вывод сделал для наглядности...
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;
}
1
x1Mike7x
218 / 131 / 6
Регистрация: 06.11.2010
Сообщений: 234
22.08.2011, 23:58 #43
Нашёл у себя в когда-то нагуглиных алгоритмах

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; 
}
1
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
23.08.2011, 10:17 #44
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Малость подумав, можно 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);
}
3
23.08.2011, 10:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2011, 10:17
Привет! Вот еще темы с ответами:

Дано натуральное число 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


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

Или воспользуйтесь поиском по форуму:
44
Ответ Создать тему
Опции темы

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