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

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

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

C++ Степень двойки
Максимальная степень двойки C++
степень двойки C++
Степень двойки в степени десятки C++
Модульное деление на степень двойки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
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
 Аватар для 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
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 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-
Не Эксперт C++
1432 / 618 / 174
Регистрация: 24.08.2014
Сообщений: 2,508
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 14:51     Найти степень двойки #10
SemenovSA, Да, но ответ должен быть 7, а у вас 6 получилось. Что-то вы упустили. Я, конечно, пытался понять это всё не расписывая каждое 16-иричное выражение на 2-ичное, но я не понимаю как работает оператор & для 16-ичных чисел. :^(
КОП
348 / 280 / 86
Регистрация: 15.08.2010
Сообщений: 755
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
Эксперт С++
4841 / 2980 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
16.03.2016, 18:29     Найти степень двойки #13
Цитата Сообщение от GbaLog- Посмотреть сообщение
но я не понимаю как работает оператор & для 16-ичных чисел. :^(
Так же как и для любых других.
GbaLog-
Не Эксперт C++
1432 / 618 / 174
Регистрация: 24.08.2014
Сообщений: 2,508
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 18:42     Найти степень двойки #14
castaway, Для вас, возможно, это очевидно, но я не понимаю, как так же? Я понимаю, что 1 & 0 = 0, но я не понимаю, например, как С & 6 = 4.
Если есть какой-то определенный алгоритм этих вычислений(вместо тупого зазубривания), то буду рад прочесть, услышать, увидеть или воспринять любым из своих органов чувств.
КОП
348 / 280 / 86
Регистрация: 15.08.2010
Сообщений: 755
16.03.2016, 18:47     Найти степень двойки #15
GbaLog-, переводите в двоичную, считаете, переводите обратно. Больше практики и все само запомнится
С = 1100; 6 = 0110
1100 &
0110
____
0100

0100 = 4
Ferrari F1
Заблокирован
295 / 281 / 61
Регистрация: 27.01.2015
Сообщений: 1,889
Записей в блоге: 1
Завершенные тесты: 1
16.03.2016, 18:51     Найти степень двойки #16
Цитата Сообщение от GbaLog- Посмотреть сообщение
но я не понимаю, например, как С & 6 = 4.
Пусть переменная С равна 4, что в двоичном представлении равно 100, а число число 6 в двоичном представлении равно 110, то применив поразрядно к этим двум числам операцию побитового И, получим:

100
110
100

http://www.cyberforum.ru/cgi-bin/latex.cgi?{100}_{2} равно http://www.cyberforum.ru/cgi-bin/latex.cgi?{4}_{10}
castaway
Эксперт С++
4841 / 2980 / 367
Регистрация: 10.11.2010
Сообщений: 11,012
Записей в блоге: 10
Завершенные тесты: 1
16.03.2016, 18:52     Найти степень двойки #17
Цитата Сообщение от GbaLog- Посмотреть сообщение
как так же?
Всё так как описал КОП.

Добавлено через 1 минуту
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
переменная С
Насколько я понял это не переменная, а цифра. Судя по всему 16-ричной системы счисления.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2016, 18:55     Найти степень двойки
Еще ссылки по теме:

Наибольшая целая степень двойки, не превосходящая заданного числа n C++
C++ Степень двойки для отражения размера памяти
C++ Возведение двойки в большую степень (длинное число)

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

Или воспользуйтесь поиском по форуму:
GbaLog-
Не Эксперт C++
1432 / 618 / 174
Регистрация: 24.08.2014
Сообщений: 2,508
Записей в блоге: 1
Завершенные тесты: 2
16.03.2016, 18:55     Найти степень двойки #18
КОП, castaway, А, я совсем и забыл, что могу так. Вот я растяпа!
Ferrari F1, С - не переменная, надо было указать что это число 13 в 16-чной системе.
Yandex
Объявления
16.03.2016, 18:55     Найти степень двойки
Ответ Создать тему
Опции темы

Текущее время: 02:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru