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

@chember08 · Регистрация: 27.10.2010

Author24 — интернет-сервис помощи студентам

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

@M128K145 · 02.11.2010, 00:20

C++

#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 · 02.11.2010, 00:31

C

#include <stdio.h>
 
int main()
{
    unsigned N = 4096, p = 0;
    while (N >>= 1) ++p;
    printf("N = 2^%u\n", p);
    return 0;
}

@МаксимМВ · 02.11.2010, 13:17

C

#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;
}

19.03.2011, 17:51

C++

#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 · 15.03.2016, 14:21

Ну прям великие программисты. Правильно кому нужна математика, цикл это круто. двоичный логарифм равен разности десятичного логарифма от н и десятичного логарифма от 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 · 15.03.2016, 14:50

Сообщение от SemenovSA

Ну прям великие программисты. Правильно кому нужна математика, цикл это круто

Ну прям великий математик, правильно кому нужны битовые операции, ведь тяжелые логарифмы это круто.

C++

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

Не по теме:

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

@SemenovSA · 16.03.2016, 14:27

Попробую в силу своего разумения объяснить как это работает, надеюсь автор топика в противном случае меня поправит.
Первоначально определимся что мы должны найти, а должны мы найти двоичный логарифм числа, причем ответ должен быть целым.
Начнем с того простого факта, что в двоичном представлении любое целое число в степени имеет только одну битовую единицу.
Поясняю на примере
$https://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)
на всякий случай
$https://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- · 16.03.2016, 14:51

SemenovSA, Да, но ответ должен быть 7, а у вас 6 получилось. Что-то вы упустили. Я, конечно, пытался понять это всё не расписывая каждое 16-иричное выражение на 2-ичное, но я не понимаю как работает оператор & для 16-ичных чисел. :^(

@КОП · 16.03.2016, 16:25

Сообщение от 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 · 16.03.2016, 16:37

Сообщение от GbaLog-

я не понимаю как работает оператор & для 16-ичных чисел. :^(

Вот таблица истинности для И

@castaway · 16.03.2016, 18:29

Сообщение от GbaLog-

но я не понимаю как работает оператор & для 16-ичных чисел. :^(

Так же как и для любых других.

@GbaLog- · 16.03.2016, 18:42

castaway, Для вас, возможно, это очевидно, но я не понимаю, как так же? Я понимаю, что 1 & 0 = 0, но я не понимаю, например, как С & 6 = 4.
Если есть какой-то определенный алгоритм этих вычислений(вместо тупого зазубривания), то буду рад прочесть, услышать, увидеть или воспринять любым из своих органов чувств.

@КОП · 16.03.2016, 18:47

GbaLog-, переводите в двоичную, считаете, переводите обратно. Больше практики и все само запомнится
С = 1100; 6 = 0110
1100 &
0110
____
0100

0100 = 4

@Ferrari F1 · 16.03.2016, 18:51

Сообщение от GbaLog-

но я не понимаю, например, как С & 6 = 4.

Пусть переменная С равна 4, что в двоичном представлении равно 100, а число число 6 в двоичном представлении равно 110, то применив поразрядно к этим двум числам операцию побитового И, получим:

100

110

100

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{100}_{2}$ равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?{4}_{10}$

@castaway · 16.03.2016, 18:52

Сообщение от GbaLog-

как так же?

Всё так как описал КОП.

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

Сообщение от Ferrari F1

переменная С

Насколько я понял это не переменная, а цифра. Судя по всему 16-ричной системы счисления.

@GbaLog- · 16.03.2016, 18:55

КОП, castaway, А, я совсем и забыл, что могу так. Вот я растяпа!
Ferrari F1, С - не переменная, надо было указать что это число 13 в 16-чной системе.

@chember08 0 / 0 / 0 Регистрация: 27.10.2010 Сообщений: 41
		1
	Найти степень двойки 01.11.2010, 21:06. Показов 22965. Ответов 17 Метки нет (Все метки) Дано целое число N>0, являющееся некоторой степенью числа 2:N=2 ^k. Найти целое число К - показатель этой степени. Если можно на С 0

@GbaLog-
	15.03.2016, 15:12 #8
	Не по теме: Kastaneda, Вы сломали мне мозг! %-) 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	16.03.2016, 14:51	10
	SemenovSA, Да, но ответ должен быть 7, а у вас 6 получилось. Что-то вы упустили. Я, конечно, пытался понять это всё не расписывая каждое 16-иричное выражение на 2-ичное, но я не понимаю как работает оператор & для 16-ичных чисел. :^( 0

@КОП 1123 / 794 / 219 Регистрация: 15.08.2010 Сообщений: 2,185
	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

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	16.03.2016, 18:29	13
	Сообщение от GbaLog- но я не понимаю как работает оператор & для 16-ичных чисел. :^( Так же как и для любых других. 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	16.03.2016, 18:42	14
	castaway, Для вас, возможно, это очевидно, но я не понимаю, как так же? Я понимаю, что 1 & 0 = 0, но я не понимаю, например, как С & 6 = 4. Если есть какой-то определенный алгоритм этих вычислений(вместо тупого зазубривания), то буду рад прочесть, услышать, увидеть или воспринять любым из своих органов чувств. 0

@КОП 1123 / 794 / 219 Регистрация: 15.08.2010 Сообщений: 2,185
	16.03.2016, 18:47	15
	GbaLog-, переводите в двоичную, считаете, переводите обратно. Больше практики и все само запомнится С = 1100; 6 = 0110 1100 & 0110 ____ 0100 0100 = 4 1

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	16.03.2016, 18:52	17
	Сообщение от GbaLog- как так же? Всё так как описал КОП. Добавлено через 1 минуту Сообщение от Ferrari F1 переменная С Насколько я понял это не переменная, а цифра. Судя по всему 16-ричной системы счисления. 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	16.03.2016, 18:55	18
	КОП, castaway, А, я совсем и забыл, что могу так. Вот я растяпа! Ferrari F1, С - не переменная, надо было указать что это число 13 в 16-чной системе. 0