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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.68
chember08
0 / 0 / 0
Регистрация: 27.10.2010
Сообщений: 41
#1

Найти степень двойки - C++

01.11.2010, 21:06. Просмотров 3853. Ответов 17
Метки нет (Все метки)

Дано целое число N>0, являющееся некоторой степенью числа 2:N=2 ^k. Найти целое число К - показатель этой степени. Если можно на С
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2010, 21:06     Найти степень двойки
Посмотрите здесь:

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

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

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

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

Модульное деление на степень двойки - C++
Раньше я всегда использовал примерной такой подход : int mod = 8; int a = 90412488; char b = 113; int modA, modB; modA = a &...

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

Степень двойки и остаток от деления - C++
Цель: Возведите 2 в 75 степень, выведите остаток от деления полученного числа на 8^4-3 Входные данные: Нет входных данных Выходные...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт С++
8284 / 3503 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
02.11.2010, 00:20     Найти степень двойки #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
int main()
{
    int k = 1;
    int ch = 4096;
    if(ch == 0)
        return 0;
    while(!(ch>>1 & 1))
    {
        ++k;
        ch >>= 1;
    }
    std::cout<<k;
    return 0;
}
KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
02.11.2010, 00:31     Найти степень двойки #3
C
1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    unsigned N = 4096, p = 0;
    while (N >>= 1) ++p;
    printf("N = 2^%u\n", p);
    return 0;
}
МаксимМВ
C/C++
90 / 90 / 5
Регистрация: 01.07.2010
Сообщений: 281
02.11.2010, 13:17     Найти степень двойки #4
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
#include <stdio.h>
 
#define ERROR -1
 
int stdv(int i)
{
    int s=0;
    if (i<=0)
        return -1;
    while (i>1)
    {
        if (i%2==1)
            return -1;
        i>>=1;
        s++;
    }
    return s;
}
 
int main(int argc, char *argv[])
{
    int num,res;
    printf("Enter number:");
    scanf("%d",&num);
    if ((res=stdv(num))!=ERROR)
        printf("%d\n",stdv(num));
    else
    {
        fprintf(stderr,"Error!\n");
        return 1;
    }
    
    return 0;
}
G@nch:)
Сообщений: n/a
19.03.2011, 17:51     Найти степень двойки #5
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
#include <iostream>
#include <windows.h>
 
using namespace std;
 
void Digit();
 
void main()
{
    SetConsoleOutputCP(1251);
    cout<<"Определение являются ли число степенью двойки."<<endl;
    Digit();
}
 
void Digit()
{
    cout<<"Число: ";
    int digit=0;
    cin>>digit;
    int i=0;
    while(digit%2==0)
    {
        digit/=2;
        i++;
    }
    if(digit==1)
    {
        cout<<"Число является степенью двойки."<<endl;
        cout<<"Это 2 в степени "<<i<<endl;
    }
    else
        cout<<"Число не является степенью двойки."<<endl;
}
SemenovSA
37 / 3 / 0
Регистрация: 20.11.2015
Сообщений: 72
15.03.2016, 14:21     Найти степень двойки #6
Ну прям великие программисты. Правильно кому нужна математика, цикл это круто. двоичный логарифм равен разности десятичного логарифма от н и десятичного логарифма от 2
или
K=log_2(N)=ln(x)/ln(2)

ln на си double log10(double x) math.h

C
1
k=(int)(log10(N)/log10(2))
Kastaneda
Форумчанин
Эксперт С++
4511 / 2853 / 227
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 1
Завершенные тесты: 1
15.03.2016, 14:50     Найти степень двойки #7
Цитата Сообщение от SemenovSA Посмотреть сообщение
Ну прям великие программисты. Правильно кому нужна математика, цикл это круто
Ну прям великий математик, правильно кому нужны битовые операции, ведь тяжелые логарифмы это круто.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    int x = 65536;
    if (x & (x - 1)) {
        std::cout << "This number is not a power of two!" << std::endl;
        return 0;
    }
    x -= 1;
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x &= 0x0000003F;
    std::cout << x << std::endl;
}
GbaLog-
15.03.2016, 15:12
  #8

Не по теме:

Kastaneda, Вы сломали мне мозг!

SemenovSA
37 / 3 / 0
Регистрация: 20.11.2015
Сообщений: 72
16.03.2016, 14:27     Найти степень двойки #9
Попробую в силу своего разумения объяснить как это работает, надеюсь автор топика в противном случае меня поправит.
Первоначально определимся что мы должны найти, а должны мы найти двоичный логарифм числа, причем ответ должен быть целым.
Начнем с того простого факта, что в двоичном представлении любое целое число в степени имеет только одну битовую единицу.
Поясняю на примере
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
$2^1=2=b10, 2^2=4=b100, 2^3=8=b1000, и т.д.$<br />

2^1=2=b10, 2^2=4=b100, 2^3=8=b1000, и т.д.

Здесь ^ - означает возведение в степень
константа начинающая на b - двоичное представление числа

Интерес представляет 4 стока кода, а точнее
C
1
(x & (x-1))
& означает побитовое И. Напомню таблицу истинности для И

0&0=0
1&0=0
0&1=0
1&1=1

Как видно из таблицы TRUE мы получаем если совпадают 1-цы. Если мы отними 1 от b0010...0 то получим b0001...1, то есть единицы пресекается не будут и мы толучим FALSE. В противном случае получаем True и выводим сообщение о том что получить целый ответ не возможно. Пример
2^3=8 (нам нужно найти 3)

8=b1000
b1000-1=b0111
b1000&b0111=0

если например у нас число 9
9=b1001
b1001-1=b1000
b1001&b1000=b1000=true => ошибка, печатаем что число не подходит

Нам остается только определить номер разряда единицы

Дальше остальной алгоритм разберем, для кратности записи, в шенацатиричной системе. Напомню что для перевода из 0x в двоичную каждый разряд шеснацатиричной системы превращается в 4 разряда двоичной то есть 0x5=b0101 => 0x55=b0101 0101

Расмотрим что происходит с числом 128. (Как можно посчитать, его двоичный алгоритм равен 7)
на всякий случай
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
$128=b10000000=0x80$<br />

ответ для него 7 в двоичной = 111 или 0х07

и так первоначально х=0х80, в 8 строке убираем 1 получаем 0х7f или b0111 1111

разберем 9 строку
C
1
x = x - ((x >> 1) & 0x55555555);
x>>1 = 0x3f (смещение в право на 1 разряд)
0х3f&0x55...= 0x0055
x-0x0055=0x7f-0x0055=0x2A

х=0x2A

10 строка
C
1
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
(x & 0x33333333)= 0x22

((x >> 2) & 0x33333333)

(x >> 2)=0x2A>>2=0xA
((x >> 2) & 0x33333333)=0xA&0x3=0x2

(x & 0x33333333) + ((x >> 2) & 0x33333333) = 0x22+0x2=0x24

x=0x24

Цитата Сообщение от Kastaneda Посмотреть сообщение
x = (x + (x >> 4)) & 0x0F0F0F0F;
(x + (x >> 4))=0х26
(x + (x >> 4)) & 0x0F0F0F0F=0х26 & 0x0F=0х6

x=0x6

Цитата Сообщение от Kastaneda Посмотреть сообщение
x = x + (x >> 8); x = x + (x >> 16)
x=0x6+0=0x6

Цитата Сообщение от Kastaneda Посмотреть сообщение
x &= 0x0000003F;
x=x&0x3f=0x06&0x3f=0x6
GbaLog-
Любитель чаепитий
2619 / 1158 / 284
Регистрация: 24.08.2014
Сообщений: 4,220
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 14:51     Найти степень двойки #10
SemenovSA, Да, но ответ должен быть 7, а у вас 6 получилось. Что-то вы упустили. Я, конечно, пытался понять это всё не расписывая каждое 16-иричное выражение на 2-ичное, но я не понимаю как работает оператор & для 16-ичных чисел. :^(
КОП
361 / 280 / 86
Регистрация: 15.08.2010
Сообщений: 762
16.03.2016, 16:25     Найти степень двойки #11
Цитата Сообщение от SemenovSA Посмотреть сообщение
0х3f&0x55...= 0x0055
0х3f&0x55...= 0x0015
математики, они такие можно же cout в код понапихать и списать результат

Добавлено через 9 минут

Не по теме:

и да, чего мы в теме 2010 года забыли?



Добавлено через 46 минут
GbaLog-, хотя поясню на всякий логику на том же примере 128 в бинарном виде
сначала х=
10000000

x -= 1; //изменяем нули на единицы
01111111

Далее _ разделяет то, что мы рассматриваем как отдельное число.

x = x - ((x >> 1) & 0x55555555); //разбиваем биты на пары и в каждую пару записываем кол-во единиц исходного Х
0_1__1_1__1_1__1_1
01___10___10___10
(1_1 - две единички; 1+1 = 2 -> 10 в бинарной.)

x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // повторяем фокус, на этот раз разбивая число на группы из 4х битов
01_10___10_10
0011____0100
(теперь мы складываем значения пар битов, т.е. 01_10 -> 1 + 2 = 3 -> 0110)

Повторяем, пока все биты не будут просуммированы в последний байт.
x = (x + (x >> 4)) & 0x0F0F0F0F;
0011____0100
00000111
(3+4 = 7)
в этом примере дальше остались только нули
x = x + (x >> 8);
x = x + (x >> 16);

И отбрасываем все, кроме него, т.к результат < 32
x &= 0x0000003F;
Winorun
38 / 38 / 4
Регистрация: 03.05.2013
Сообщений: 177
16.03.2016, 16:37     Найти степень двойки #12
Цитата Сообщение от GbaLog- Посмотреть сообщение
я не понимаю как работает оператор & для 16-ичных чисел. :^(
Вот таблица истинности для И
Вложения
Тип файла: pdf main.pdf (15.4 Кб, 2 просмотров)
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
16.03.2016, 18:29     Найти степень двойки #13
Цитата Сообщение от GbaLog- Посмотреть сообщение
но я не понимаю как работает оператор & для 16-ичных чисел. :^(
Так же как и для любых других.
GbaLog-
Любитель чаепитий
2619 / 1158 / 284
Регистрация: 24.08.2014
Сообщений: 4,220
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 18:42     Найти степень двойки #14
castaway, Для вас, возможно, это очевидно, но я не понимаю, как так же? Я понимаю, что 1 & 0 = 0, но я не понимаю, например, как С & 6 = 4.
Если есть какой-то определенный алгоритм этих вычислений(вместо тупого зазубривания), то буду рад прочесть, услышать, увидеть или воспринять любым из своих органов чувств.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2016, 18:47     Найти степень двойки
Еще ссылки по теме:

Возведение двойки в 40-вую и более степень - C++
Здравствуйте! Нужно реализовать возведение двойки в 40-вую и более степень. Вот мой код С++: #include &lt;iostream&gt; using namespace...

Степень двойки для отражения размера памяти - C++
Коллеги глупый но все же интересный вопрос! Один гибибайт состоит из 1073741824 байт памяти. Почему разработчики выбрали такое странное...

Возведение двойки в большую степень (длинное число) - C++
Добрый день всем, помогите пожалуйста разобраться с проблемой. необходимо возвести двойку в степень (в конечном итоге 2 в 512, например) ...

Сделать с помощью массива возведение двойки в произвольную степень. - C++
Пользователь вводит число, программа выводит 2 в этой степени, т.е. пользователь вводит N, и 2 возводится в степень N. (сам бы сделал,...

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


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

Или воспользуйтесь поиском по форуму:
КОП
361 / 280 / 86
Регистрация: 15.08.2010
Сообщений: 762
16.03.2016, 18:47     Найти степень двойки #15
GbaLog-, переводите в двоичную, считаете, переводите обратно. Больше практики и все само запомнится
С = 1100; 6 = 0110
1100 &
0110
____
0100

0100 = 4
Yandex
Объявления
16.03.2016, 18:47     Найти степень двойки
Ответ Создать тему
Опции темы

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