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

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

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

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

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

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

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

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

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

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

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

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

17
M128K145
Эксперт С++
8297 / 3517 / 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;
}
1
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;
}
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;
}
0
G@nch:)
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))
0
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,357
Записей в блоге: 2
Завершенные тесты: 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;
}
0
GbaLog-
15.03.2016, 15:12
  #8

Не по теме:

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

0
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
0
GbaLog-
Любитель чаепитий
3031 / 1399 / 338
Регистрация: 24.08.2014
Сообщений: 4,972
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 14:51 #10
SemenovSA, Да, но ответ должен быть 7, а у вас 6 получилось. Что-то вы упустили. Я, конечно, пытался понять это всё не расписывая каждое 16-иричное выражение на 2-ичное, но я не понимаю как работает оператор & для 16-ичных чисел. :^(
0
КОП
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;
1
Winorun
38 / 38 / 4
Регистрация: 03.05.2013
Сообщений: 177
16.03.2016, 16:37 #12
Цитата Сообщение от GbaLog- Посмотреть сообщение
я не понимаю как работает оператор & для 16-ичных чисел. :^(
Вот таблица истинности для И
1
Вложения
Тип файла: pdf main.pdf (15.4 Кб, 2 просмотров)
castaway
Эксперт С++
4915 / 3023 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
16.03.2016, 18:29 #13
Цитата Сообщение от GbaLog- Посмотреть сообщение
но я не понимаю как работает оператор & для 16-ичных чисел. :^(
Так же как и для любых других.
0
GbaLog-
Любитель чаепитий
3031 / 1399 / 338
Регистрация: 24.08.2014
Сообщений: 4,972
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 18:42 #14
castaway, Для вас, возможно, это очевидно, но я не понимаю, как так же? Я понимаю, что 1 & 0 = 0, но я не понимаю, например, как С & 6 = 4.
Если есть какой-то определенный алгоритм этих вычислений(вместо тупого зазубривания), то буду рад прочесть, услышать, увидеть или воспринять любым из своих органов чувств.
0
КОП
361 / 280 / 86
Регистрация: 15.08.2010
Сообщений: 762
16.03.2016, 18:47 #15
GbaLog-, переводите в двоичную, считаете, переводите обратно. Больше практики и все само запомнится
С = 1100; 6 = 0110
1100 &
0110
____
0100

0100 = 4
1
16.03.2016, 18:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2016, 18:47
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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