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

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

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

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

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

Вычислить 10-ю степень двойки сложением, умножением и просто возведением в степень. - C++
Написать код на С++ или С# или на Java Вычислить 10-ю степень двойки 1 - сложением, умножением и просто возведением в степень.

Проверить, верно ли, что целая и дробная части заданного вещественного числа одинаковы - C++
Задача: Вывести true если высказывание верно, false в противном случае . Целая и дробная части заданного вещественного числа одинаковы....

Найти количество способов представления заданного числа N в виде суммы степеней двойки - C++
Всем привет. Задача звучит так: Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых...

Реализовать рекурсивную функцию возведения заданного числа в степень n - C++
Напишите рекурсивную функцию int power(int a, int n) которая считает a^n. (a степень n) примеры для проверки 1)220 0 1 ...

степень двойки - C++
Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе. int a,b=1; cin&gt;&gt;a; for(;;) { b=b*2; ...

Степень двойки - C++
Изучаю программирование. Попытался решить известную задачу. Программа компилируется, но если ввести к примеру 8 она выдает &quot;no&quot;. В чем я...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.02.2013, 19:47 #2
http://www.cyberforum.ru/cpp-experts...ml#post1708284
0
Asker
115 / 103 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 19:57  [ТС] #3
Там не совсем то. Мне наибольшую надо найти
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.02.2013, 20:11 #4
Цитата Сообщение от Asker Посмотреть сообщение
ам не совсем то. Мне наибольшую надо найти
там упрощенное нахождение степени двойки, ваша задача в цикле начиная с n проверять является ли число степенью двойки, если нет, уменьшить n на еденицу и перейти на следующую итерацию
0
abit
262 / 261 / 33
Регистрация: 03.02.2013
Сообщений: 722
04.02.2013, 20:15 #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)
0
Asker
115 / 103 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 20:15  [ТС] #6
Jupiter, это если я введу число 224 - 1 = 16 777 216, то что же, по циклу перебирать 8 388 607 чисел? Наверно, есть способ побыстрее, вот только какой?
0
abit
262 / 261 / 33
Регистрация: 03.02.2013
Сообщений: 722
04.02.2013, 20:21 #7
Цитата Сообщение от Asker Посмотреть сообщение
Jupiter, это если я введу число 224 - 1 = 16 777 216, то что же, по циклу перебирать 8 388 607 чисел? Наверно, есть способ побыстрее, вот только какой?
на моём примере ваш цикл выполниться за 24 хода, без умножений и делений

да, и юзайте не pow, а ts = (2 << n-1); тогда в ts будет нужное вам число
0
Nick Alte
Эксперт С++
1637 / 1009 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
04.02.2013, 20:25 #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;
}
1
Asker
115 / 103 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 21:15  [ТС] #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 рублей
0
abit
262 / 261 / 33
Регистрация: 03.02.2013
Сообщений: 722
04.02.2013, 21:16 #10
abit, Вы используете возведение в степень, а она очень тяжело работает...
я же сказал, что можно заменить pow на (1 << (n-1))
0
Nick Alte
Эксперт С++
1637 / 1009 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
04.02.2013, 21:27 #11
Цитата Сообщение от Asker Посмотреть сообщение
я думаю так быстрее будет на уровне машинного кода
Зачем впустую думать, когда можно проверить?
0
Asker
115 / 103 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 21:39  [ТС] #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 Посмотреть сообщение
Зачем впустую думать, когда можно проверить?
А как проверить? мне интересно, где истина
0
Nick Alte
Эксперт С++
1637 / 1009 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
04.02.2013, 21:57 #13
Цитата Сообщение от Asker Посмотреть сообщение
А как проверить?
Как учат нас Разрушители Мифов - экспериментально. Замерить время работы обоих вариантов при максимальной оптимизации и сравнить. Или выгнать в ассемблерный листинг и опять же сравнить.
0
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
04.02.2013, 21:57 #14
А логарифм можно использовать? Если да тогда double к int, а потом 2 << ( результат - 1 )
0
Asker
115 / 103 / 11
Регистрация: 18.12.2010
Сообщений: 378
04.02.2013, 22:27  [ТС] #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. при эксперименте я это исправил. Во время эксперимента выгрузил из винды посторонние проги и даже мышой не шевелил для чистоты эксперимента
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2013, 22:27
Привет! Вот еще темы с ответами:

Максимальная степень двойки - C++
&quot;F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b и F(a, b) = -1, если a = b.&quot; Это как...

Точная степень двойки - C++
Само задание: Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. ...

Найти степень двойки - C++
Дано целое число N&gt;0, являющееся некоторой степенью числа 2:N=2 ^k. Найти целое число К - показатель этой степени. Если можно на С

Степень двойки в степени десятки - C++
Допустим, есть большое число типа double или extended. Дана степень десятки: 1Е+228. 1Е+228=2760. Вот задача: Сколько степеней двойки в...


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

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

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