Найти наибольшую степень двойки, на которую будет делиться введенное число

@DaniilDemchenko · Регистрация: 02.02.2020

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

Здравствуйте! Помогите, пожалуйста, перевести программу из С# в С++

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void Main(string[] args)
        {
            Console.Write("Введите число а: ");
            int a = int.Parse(Console.ReadLine());
            int result = 0;
 
            for (int temp = 2; temp <= a; temp *= 2)
                if (a % temp == 0)
                    result = temp;
 
            if (result != 0)
                Console.WriteLine("Наибольшая степень числа 2, делящая данное целое число {0} = {1}", a, result);
            else
                Console.WriteLine("Результат не найден.");
 
            Console.ReadKey();
        }

@FFPowerMan · 09.12.2021, 13:03

Вы мой код смотрели. Посмотрите повнимательнее. int состоит из 4 байт, поэтому биты нумеруются у него с 0 до 31, СПРАВА НАЛЕВО. Поэтому в моей программе 1 сразу задвигаем на левый край, получаем число, это максимальная степень двойки.
1 2 4 8 Посмотрите как эти числа в бинарном(двоичном) представлении, это просто 1 сдвинутая на сколько-то разрядов вправо. Для этого служат операторы сдвига << и >>.
Делим его и смотрим остаток это операция %. Опять же читайте документацию.
Если остаток есть, то программа продолжит свою работу, т.е. сдвигаем max на 1 вправо и снова делим.
Если поделилось без остатка то break; выход из цикла.

@DaniilDemchenko · 09.12.2021, 13:04 **[ТС]**

Volga_, ДАА, спасибо огромное вам, только на выход идет не p, а i. Все работает, огромное спасибо. А можете обьяснить, что в коде Folian? И как он будет выглядеть, так скажем, в общем коде?(имею ввиду, я так понимаю, что это лишь часть кода, а как будет выглядеть полноценный код с частью кода Folian). Это уже для общего развития, так сказать

@Volga_ · 09.12.2021, 13:10

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

А можете обьяснить, что в коде Folian? И как он будет выглядеть, так скажем, в общем коде?(имею ввиду, я так понимаю, что это лишь часть кода, а как будет выглядеть полноценный код с частью кода Folian).

Можно посмотрите: https://iq.opengenus.org/detec... operators/
И он обязательно объяснит вам все.

@DaniilDemchenko · 09.12.2021, 13:21 **[ТС]**

FFPowerMan, извините, но это для меня прям сложно пока что) Я правильно понял, что нумерация идет справа налево, то есть, с 31(лево) до 0(право). Потом вы сделали 1-цу последней в этой нумерации, убрав ноль. Про бинарное представление понял, от 0001 до 1000. Все, понял, спасибо) Только max на вывод не надо (там вообще какие-то числа миллиардного разряда), ну и вместо самого числа (в случае с 1000 на вывод пошло число 8) нужно, чтобы пошла степень, но я думаю, что это поправимо. Спасибо вам за ваши труды!

Добавлено через 48 секунд
ВСЕМ ОГРОМНОЕ СПАСИБО ЗА ПОМОЩЬ!

Добавлено через 1 минуту
Volga_, от блин, все на английском( Ладно, все равно спасибо, переводчик встроенный есть, должен справиться

@_Ivana · 09.12.2021, 13:22

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

Это хороший код как я понимаю.

Это тривиальный и не оптимальный кот. Хороший кот - в главе "Подсчет завершающих нулевых битов" в книге Генри Уоррена "Хакерз Делайт"

@Folian · 09.12.2021, 14:04

Почитал тут.

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

что в коде Folian

Примерно то же что и у ув-го liv, только без ошибок. И тебе нужен именно его вариант со счётчиком.

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

Хороший кот - в главе "Подсчет завершающих нулевых битов" в книге Генри Уоррена "Хакерз Делайт"

Там их даж несколько. Интересная книжка.

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
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
 
int foo(int n)
{
    //  if(!n) inf??
    if(!n)
    {
        std::cout << "inf";
        return -1;
    }
 
    int count { 0 };
    int pwr { 1 };
    while(!(pwr & n))
    {
        pwr <<= 1;
        ++count;
    }
 
    return count;
}
 
int bar(unsigned x)
{
    int n {};
    x = ~x & (x - 1);
    while(x)
    {
        ++n;
        x >>= 1;
    }
    return n;
}
 
int main()
{
    //int n {};
    //std::cin >> n;
 
    for(int i { 0 }; i < 260; ++i)
        std::cout << i << " : " << foo(i) << " " << bar(i) << "\n";
 
 
    return 0;
}

@FFPowerMan · 09.12.2021, 14:24

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

нумерация идет справа налево, то есть, с 31(лево) до 0(право).

- Да.

Добавлено через 44 секунды

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

убрав ноль.

- ничего не убирается, просто условие.

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

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

какие-то числа миллиардного разряда),

- ну естественно, целое до 2'147'483'647.

@повар1 · 09.12.2021, 14:42

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
 
int main() {
    int n,i=0,a;
 
    cin>>n;
    while((1<<i)<=n)
       n%(1<<i)==0 ? a=i++: i++;
    cout<<(1<<a)<<"(i="<<a<<")";
    return 0;
}

@_Ivana · 09.12.2021, 17:00

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

Там их даж несколько. Интересная книжка.

Воистину. Только вы почему-то настойчиво продолжаете везде пихать

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

while

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

Хороший кот

вот, например

C++
1
2
3
int m[] = {0, 1, 26, 2, 23, 27, 32, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18, 0};
 
int t(unsigned n) { return m[((n ^ (n-1)) >> 1) % 37]; }

как тебе такое, ~~Илон Маск~~ Folian?

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

мне его подсказал преподаватель

если хотите сдать и забыть, то пойдет что угодно. Если хотите научиться - найдите нормального преподавателя.

@lemegeton · 09.12.2021, 17:17

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

while (n % 2 == 0)

Как думаете, быстрее будет "n & 1 == 0"?

@Folian · 09.12.2021, 17:28

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

Только вы почему-то настойчиво продолжаете везде пихать

Я тупо взял самый короткий, т.к. с пдф не копипастится и лень

Прошёлся по диагонали только; вечером время останется если - почитаю, пока некогда.

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

как тебе такое

Ну такое, да) только откуда 37? Загадочное число)

@_Ivana · 09.12.2021, 17:41

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

Ну такое, да) только откуда 37? Загадочное число)

А этого у Уоррена и нет. Но у нас же и свои мозги есть, не только копипастить можем

Все то, что до % 37 - это выставленные единичные биты на том месте, где были начальные нули, а все остальные единицы занулены. Тривиальное преобразование через - 1 (получаем различие в младших нулевых разрядах) и ксор с исходным значением со сдвигом вправо как раз оставляет нам только нужные единицы. А далее остается только их посчитать. Но мы же не глупые студенты, мы не будем считать их через while. Уоррен считает их через бинарный поиск. Уже лучше, но мы чуть-чуть подумаем как можно улучшить. У нас получается всего 32 различных аргумента: 0...01, 0...011 и т.п. И надо для каждого из этих аргументов вернуть число единиц в нем. Можно запихнуть в мапку, но это из пушки по воробьям и не спортивно

Предположим, что есть какое-то магическое число, которое будет давать уникальный остаток от деления всех этих возможных аргументов на себя. И если оно не очень велико, мы просто захардкодим массив, где по индексу - остатку от деления аргумента на это число будет лежать количество единичных бит аргумента. Делаем тривиальную проверку (написав простейший тестирующий кот) - вуаля, это число 37! Ближайшее простое число, большее 32. Можем позволить себе отрезать памяти на 37 интов для оптимизации расчетов. А дырки (несущеструющие остатки от деления аргументов на 37) заполняем чем угодно (например, нулями) - все равно они у нас не встретятся при работе функции.

@Folian · 13.12.2021, 21:44

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

Ближайшее простое число, большее 32.

Ага! Смысл ясен.

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

C++
1
((n ^ (n-1)) >> 1) % 37

Только тут, походу, проблемка с нулём будет: от сдвига его колбасит и вылезает 31.
От такое (как раз из книжки) тож самое выдаёт, но без сдвигов ~val & (val - 1)

Для 64 наковырял подобную, вроде работает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint32_t foo(uint64_t val)
{
    enum magic { sixseven = 67 };
 
    const uint32_t arr[magic::sixseven] {0, 1, 39, 2, 15, 40, 23, 3, 12, 16,
        59, 41, 19, 24, 54, 4, 
        64 /*эта долька для ноля*/,
        13, 10, 17, 62, 60, 28, 42, 30, 20,
        51, 25, 44, 55, 47, 5, 32, 0, 38, 14, 22, 11, 58, 18, 53, 63,
        9, 61, 27, 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45,
        36, 56, 7, 48, 35, 6, 34, 33, 0 };
 
    return arr[(~val & (val - 1)) % magic::sixseven];
}

@_Ivana · 13.12.2021, 21:53

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

Ага! Смысл ясен.

Да, только хорошо бы проверить уникальность остатков от деления на 67 - про ближайшее большее простое число это гипотеза, я ее не доказывал

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

Только тут, походу, проблемка с нулём будет: от сдвига его колбасит и вылезает 31

Да, но это никакая не проблема - просто на нуле эта функция не определена (ноль делится нацело на любую степень двойки), так что там хоть 31, хоть 32 - все равно неправильно и не будем вообще ее на нуле вызывать

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

От такое (как раз из книжки) тож самое выдаёт, но без сдвигов ~val & (val - 1)

Вполне возможно, просто ксорный вариант я сам придумал, наверное у Уоррена этот получше

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

Для 64 наковырял подобную, вроде работает

(хотел смайлик с огнем, но его нет)

@Folian · 13.12.2021, 22:09

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

хорошо бы проверить уникальность остатков

У меня тоже были сомнения и я проверял (тупил "вручную" под чаёк, очень успокаивает

)

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

Да, но это никакая не проблема - просто на нуле эта функция не определена (ноль делится нацело на любую степень двойки), так что там хоть 31, хоть 32 - все равно неправильно и не будем вообще ее на нуле вызывать

В рамках задачи - да, но хотелось покрасивше; да и в рамках вообще хорошо когда есть определённость и можно обработать как нужно

@_Ivana · 13.12.2021, 22:15

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

В рамках задачи - да, но хотелось покрасивше

Ну да, согласен, вариант Уоррена красивше моего при тех же затратах на число операций. В общем, вроде осилили задачу. По-хорошему надо помнить про уровни кеша проца и необходимость лазить в память за массивом, даже если он статический, и что на деле алгоритм с бинарным поиском может быть быстрее, ибо не надо лазить в память а хватит регистров, да и остаток от деления не везде искоробки в командах проца / арифметитческого сопроца есть, но это уже для совсем настоящего программирования. Для учебной задачи имхо достаточно красиво

Новые блоги и статьи Все статьи Все блоги /
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .

@FFPowerMan 2163 / 1241 / 511 Регистрация: 11.10.2018 Сообщений: 6,370
	09.12.2021, 13:03
	Вы мой код смотрели. Посмотрите повнимательнее. int состоит из 4 байт, поэтому биты нумеруются у него с 0 до 31, СПРАВА НАЛЕВО. Поэтому в моей программе 1 сразу задвигаем на левый край, получаем число, это максимальная степень двойки. 1 2 4 8 Посмотрите как эти числа в бинарном(двоичном) представлении, это просто 1 сдвинутая на сколько-то разрядов вправо. Для этого служат операторы сдвига << и >>. Делим его и смотрим остаток это операция %. Опять же читайте документацию. Если остаток есть, то программа продолжит свою работу, т.е. сдвигаем max на 1 вправо и снова делим. Если поделилось без остатка то break; выход из цикла. 1

@DaniilDemchenko 3 / 3 / 0 Регистрация: 02.02.2020 Сообщений: 69
	09.12.2021, 13:04 [ТС]
	Volga_, ДАА, спасибо огромное вам, только на выход идет не p, а i. Все работает, огромное спасибо. А можете обьяснить, что в коде Folian? И как он будет выглядеть, так скажем, в общем коде?(имею ввиду, я так понимаю, что это лишь часть кода, а как будет выглядеть полноценный код с частью кода Folian). Это уже для общего развития, так сказать 0

@DaniilDemchenko 3 / 3 / 0 Регистрация: 02.02.2020 Сообщений: 69
	09.12.2021, 13:21 [ТС]
	FFPowerMan, извините, но это для меня прям сложно пока что) Я правильно понял, что нумерация идет справа налево, то есть, с 31(лево) до 0(право). Потом вы сделали 1-цу последней в этой нумерации, убрав ноль. Про бинарное представление понял, от 0001 до 1000. Все, понял, спасибо) Только max на вывод не надо (там вообще какие-то числа миллиардного разряда), ну и вместо самого числа (в случае с 1000 на вывод пошло число 8) нужно, чтобы пошла степень, но я думаю, что это поправимо. Спасибо вам за ваши труды! Добавлено через 48 секунд ВСЕМ ОГРОМНОЕ СПАСИБО ЗА ПОМОЩЬ! Добавлено через 1 минуту Volga_, от блин, все на английском( Ладно, все равно спасибо, переводчик встроенный есть, должен справиться 0