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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.93
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
#1

Наибольшая целая степень двойки, не превосходящая заданного числа n - C++

04.02.2013, 19:36. Просмотров 2012. Ответов 15
Метки нет (Все метки)

Мне нужно рассчитать наибольшую целую степень двойки, не превосходящую заданного числа n.
Например,
ввод 101
вывод 64

Есть код, который это делает:
C++
1
2
3
4
5
6
...
int n, t=1;
cin >> n;
for (;t<n;) t*=2;
cout << t/2;
...
, но в нём используются циклы, и он довольно медленный.
Кто знает, как можно сделать это еще быстрее (скорость принципиальна)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2013, 19:36     Наибольшая целая степень двойки, не превосходящая заданного числа n
Посмотрите здесь:

C++ Сформировать текстовый файл-таблицу возведения в степень 2 и 3, целых чисел от 1 до заданного с консоли числа
C++ Найти степень двойки
C++ Степень двойки
Максимальная степень двойки C++
C++ Найти количество способов представления заданного числа N в виде суммы степеней двойки
степень двойки C++
Степень двойки в степени десятки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт С++
6550 / 3970 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.02.2013, 19:47     Наибольшая целая степень двойки, не превосходящая заданного числа n #2
http://www.cyberforum.ru/cpp-experts...ml#post1708284
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 19:57  [ТС]     Наибольшая целая степень двойки, не превосходящая заданного числа n #3
Там не совсем то. Мне наибольшую надо найти
Jupiter
Каратель
Эксперт С++
6550 / 3970 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.02.2013, 20:11     Наибольшая целая степень двойки, не превосходящая заданного числа n #4
Цитата Сообщение от Asker Посмотреть сообщение
ам не совсем то. Мне наибольшую надо найти
там упрощенное нахождение степени двойки, ваша задача в цикле начиная с n проверять является ли число степенью двойки, если нет, уменьшить n на еденицу и перейти на следующую итерацию
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
04.02.2013, 20:15     Наибольшая целая степень двойки, не превосходящая заданного числа n #5
Цитата Сообщение от Asker Посмотреть сообщение
Мне нужно рассчитать наибольшую целую степень двойки, не превосходящую заданного числа n.
Например,
ввод 101
вывод 64

Есть код, который это делает:
C++
1
2
3
4
5
6
...
int n, t=1;
cin >> n;
for (;t<n;) t*=2;
cout << t/2;
...
, но в нём используются циклы, и он довольно медленный.
Кто знает, как можно сделать это еще быстрее (скорость принципиальна)
как минимум сходу можно заменить t*=2; на t=t<<1; сдвиг на порядок живее работает
потом у вас выводится не сама степень двойки а 2^(n-1), впринципе я бы двигал t, а не n:

C++
1
2
3
4
5
6
int t;
cin >> t;
int ts=t;
int n=0;
 
while (ts!=0) { ts=ts>>1; ++n;}
как-то так, на выходе будет чистая n

pow(2,n-1) соответственно даст Ваш 2^(n-1)
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 20:15  [ТС]     Наибольшая целая степень двойки, не превосходящая заданного числа n #6
Jupiter, это если я введу число 224 - 1 = 16 777 216, то что же, по циклу перебирать 8 388 607 чисел? Наверно, есть способ побыстрее, вот только какой?
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
04.02.2013, 20:21     Наибольшая целая степень двойки, не превосходящая заданного числа n #7
Цитата Сообщение от Asker Посмотреть сообщение
Jupiter, это если я введу число 224 - 1 = 16 777 216, то что же, по циклу перебирать 8 388 607 чисел? Наверно, есть способ побыстрее, вот только какой?
на моём примере ваш цикл выполниться за 24 хода, без умножений и делений

да, и юзайте не pow, а ts = (2 << n-1); тогда в ts будет нужное вам число
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
04.02.2013, 20:25     Наибольшая целая степень двойки, не превосходящая заданного числа n #8
Способ, конечно, есть. Сдвигать число на один разряд, пока оно не превратится в 0 и накапливать результаты операцией OR. Получится минимальная степень двойки, превышающая заданное число, за вычетом единицы. Сдвигаем результат и добавляем единицу - получаем искомое.
C++
1
2
3
4
5
6
7
unsigned int maxpot(unsigned int n)
{
    unsigned int rv = 0;
    for(; n; n <<= 1)
        rv |= n;
    return (rv >> 1) + 1;
}
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 21:15  [ТС]     Наибольшая целая степень двойки, не превосходящая заданного числа n #9
Nick Alte, это то, что нужно
Только у Вас небольшая опечатка, из-за которой функция не работала:
C++
1
2
3
4
5
6
7
unsigned int maxpot(unsigned int n)
{
    unsigned int rv = 0;
    for(; n; n >>= 1) // здесь сдвиг вправо, а не влево
        rv |= n;
    return (rv >> 1) + 1;
}
Но принцип понятен. Быстрее уже, наверно, нельзя...

Добавлено через 4 минуты
abit, Вы используете возведение в степень, а она очень тяжело работает...

Добавлено через 3 минуты
Хотя нет! если объединить присваивания, а вместо цикла for написать while, я думаю так быстрее будет на уровне машинного кода:
C++
1
2
3
4
5
6
unsigned int maxpot(unsigned int n)
{
unsigned int rv = 0;
while (n) rv |= n >>= 1;
return ++rv;
}
кто предложит более быстрый вариант - тому дам 100 рублей
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
04.02.2013, 21:16     Наибольшая целая степень двойки, не превосходящая заданного числа n #10
abit, Вы используете возведение в степень, а она очень тяжело работает...
я же сказал, что можно заменить pow на (1 << (n-1))
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
04.02.2013, 21:27     Наибольшая целая степень двойки, не превосходящая заданного числа n #11
Цитата Сообщение от Asker Посмотреть сообщение
я думаю так быстрее будет на уровне машинного кода
Зачем впустую думать, когда можно проверить?
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 21:39  [ТС]     Наибольшая целая степень двойки, не превосходящая заданного числа n #12
Хотя... если переделать мой самый первый вариант (вместо умножения - сдвиг). А вот интересно, что быстрее:
Это
C++
1
2
3
4
int n, t=1;
cin >> n;
while (t<n) t <<= 2;
cout << (t >>= 2);
или это
C++
1
2
3
4
5
int n;
unsigned int rv = 0;
cin >> n;
while (n) rv |= n >>= 1;
cout << ++rv;


Добавлено через 27 секунд
Цитата Сообщение от Nick Alte Посмотреть сообщение
Зачем впустую думать, когда можно проверить?
А как проверить? мне интересно, где истина
Nick Alte
Эксперт С++
1605 / 997 / 118
Регистрация: 27.09.2009
Сообщений: 1,923
Завершенные тесты: 1
04.02.2013, 21:57     Наибольшая целая степень двойки, не превосходящая заданного числа n #13
Цитата Сообщение от Asker Посмотреть сообщение
А как проверить?
Как учат нас Разрушители Мифов - экспериментально. Замерить время работы обоих вариантов при максимальной оптимизации и сравнить. Или выгнать в ассемблерный листинг и опять же сравнить.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
04.02.2013, 21:57     Наибольшая целая степень двойки, не превосходящая заданного числа n #14
А логарифм можно использовать? Если да тогда double к int, а потом 2 << ( результат - 1 )
Asker
114 / 102 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 22:27  [ТС]     Наибольшая целая степень двойки, не превосходящая заданного числа n #15
Это подойдет?

Добавлено через 25 минут
Люди, я провел эксперимент. Я перебрал все числа от 2 до 1000000 и искал требуемую степень двойки, используя сначала первый способ, затем второй

Я запустил на Visual C++ сначала этот код:
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
#include <iostream>
#include <time.h>
 
using namespace std;
 
int main()
{
clock_t time;
time = clock();
int n;
 
int t=1;
 
for (int i=2; i<1000000; i++)
{
n=i;
t=1;
while (t<n) t<<=1;
cout << (t>>=1) << endl;
}
 
time = clock() - time;
cout << ((double)time/CLOCKS_PER_SEC); 
system("pause");
return 0;
}
В конце мне прога выдала результат: 114.782

Потом я запустил этот код:

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
#include <iostream>
#include <time.h>
 
using namespace std;
 
int main()
{
clock_t time;
time = clock();
int n;
 
unsigned int rv;
 
for (int i=2; i<1000000; i++)
{
n=i;
rv=0;
while (n) rv |= n >>= 1;
cout << ++rv << endl;
}
 
time = clock() - time;
cout << ((double)time/CLOCKS_PER_SEC); 
system("pause");
return 0;
}
И мне прога выдала результат: 123.422

Значит ли это, что первый способ был быстрее? о.О

ЗЫ. В посту #12 я ошибся, сдвигая на 2 разряда, а не на 1. при эксперименте я это исправил. Во время эксперимента выгрузил из винды посторонние проги и даже мышой не шевелил для чистоты эксперимента
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2013, 23:01     Наибольшая целая степень двойки, не превосходящая заданного числа n
Еще ссылки по теме:

Модульное деление на степень двойки C++
Точная степень двойки C++
C++ Возведение двойки в 40-вую и более степень
C++ Степень двойки и остаток от деления
Реализовать рекурсивную функцию возведения заданного числа в степень n C++

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

Или воспользуйтесь поиском по форуму:
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
04.02.2013, 23:01     Наибольшая целая степень двойки, не превосходящая заданного числа n #16
Как вариант:
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
#include <iostream>
 
 
int main() {
   int power = 1;
   int n = 45;
   
   if ( n >= power << 16 )
      power <<= 16;
   
   if ( n >= power << 8 )
      power <<= 8;
   
   if ( n >= power << 4 )
      power <<= 4;
   
   if ( n >= power << 2 )
      power <<= 2;
   
   if ( n >= power << 1 )
      power <<= 1;
   
   std::cout << power << std::endl;
   
   return 0;
}
Yandex
Объявления
04.02.2013, 23:01     Наибольшая целая степень двойки, не превосходящая заданного числа n
Ответ Создать тему
Опции темы

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