Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283

Как распараллелить определение является ли число степенью двойки

25.12.2018, 11:22. Показов 1821. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Все числа большие, целые и положительные.

C++
1
2
3
4
5
6
7
8
9
10
    bool BigInt::isPowerOfTwo(const BigInt &x)
    {
        if (x.a[0] & 1 == 1) // если число не чётное - до свидания
            return false;
 
        BigInt v = x; v.sign = positive;
        while ((  (v.a[0] & 1) == 0) && v > 1) /* делим v на 2 пока оно чётное и > 1 */
            v /= (unsigned int)2;
        return (v == 1);
    }
Теоретически, всё работает. Уже несколько часов. Причём трудится только одно ядро процессора.
Остальные 7 ядер нагло увиливают от работы.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.12.2018, 11:22
Ответы с готовыми решениями:

Как на стадии компиляции проверить что число является степенью двойки
Очень простой вопрос - как на стадии компиляции проверить что число является степенью двойки? Как проверить на стадии исполнения знаю, но...

Является ли число степенью двойки
Условие: Входные данные Входной файл INPUT.TXT содержит единственное целое число N, не превосходящее 10000 по абсолютной величине. ...

Является ли число степенью двойки
не понимаю в чём ошибка вроде все условия соблюдены. есть чисел вида 2K, где K – некоторое неотрицательное целое число. Назовем такие...

20
 Аватар для SerVal
37 / 36 / 9
Регистрация: 16.04.2015
Сообщений: 283
26.12.2018, 09:54  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Ygg Посмотреть сообщение
Если ничего не путаю, то оно запишется в BigInt как две ячейки. Старшая ячейка 2, младшая 147'483'648.
Да.

С Вашим числом 2147483648 получилось.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    BigInt A = 2147483648L;
    A.printInfo();
 
    double LG10N = log10(2) + 9;
    double LG2N = LG10N / log10(2);
    unsigned long exp = round(LG2N);
    BigInt result = BigInt::pow2(exp);
 
    while (result < A)
    {
        result *= (unsigned int)2;
    }
 
    if (result == A) std::cout << "Number is power of two."     << std::endl;
    else             std::cout << "Number is NOT power of two." << std::endl;
Результат:
C++
1
2
3
4
5
D:\aProjects\TestBigInt\x64\Release>TestBigInt.exe
 big integer :  2147483648
 number of decimal digits = 10
 number of segments       = 2
Number is power of two.
Правда, непонятно, откуда взялась девятка. И что вместо неё должно быть для большого числа.
*число цифр и сегментов в BigInt вычисляются мгновенно.

Добавлено через 10 часов 49 минут
Вроде бы получилось. Вот окончательный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LG10N = log10(<старший элемент вектора>) + 9*(<количество элементов в векторе> - 1).
 
bool    isPowerOfTwo(const BigInt &A)
{
    if (A.a[0] & 1 == 1) return false; // не чётное число
 
    unsigned int high_element_value = A.a[A.a.size() - 1];
 
    double LG10N = std::log10(high_element_value) + 9 * (A.a.size() - 1);
 
    double LG2N = LG10N / std::log10(2);
    unsigned long exp = round(LG2N);
    BigInt result = BigInt::pow2(exp);
 
    while (result < A)
    {
        result *= (unsigned int)2;
    }
 
    if (result == A) return true;
    return false;
}
Всем откликнувшимся ОГРОМНОЕ спасибо. Правда, надо будет написать какой-нибудь тестик для проверки isPowerOfTwo.
А пока поставил проверять недавно найденное новое число Мерсена.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
D:\aProjects\TestBigInt\x64\Release>TestBigInt.exe -isPrime "2^82589933-1"
 
 Generating number 2^82589933-1
 big integer :  1488944 ... 217902591
 number of decimal digits = 24862048
 number of segments       = 2762450
 time : 95.208 sec.
 
 --- Primality test ---
 
 Trial division
 Создаём список простых чисел меньших 1000000
 Пробуем поделить кандидата на 78498 простых чисел.
 
 The divisor is not found. Perhaps this is a prime number.
 time : 1231.71 sec.
 
 Checking, is the candidate "Mersenn number" ?
 Проверяем, является ли кандидат числом Мерсена.
 time : 95.209 sec.
 
 The number is Mersenn number, starting Lucas-Lemher test.
 Lucas-Lehmer primality test.
Работает уже 10 часов на Core Quad 9650. Похоже Lucas-Lehmer тест тоже надо подрихтовать.
Или добавить какой-нибудь индикатор прогресса.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.12.2018, 09:54
Помогаю со студенческими работами здесь

Является ли число степенью двойки
Дано натуральное число n. Определите, является ли оно степенью числа 2, и выведете слово YES если является,и выведите слово NO если не...

Является ли число степенью двойки?
Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе.

Проверить, является ли число степенью двойки
Если число степень 2, то ДА, иначе НЕТ. #include &lt;fstream&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int main()...

Определить, является ли число степенью двойки
Такая проблема: в проге мне нужно задать количество чисел которые я введу (т.е создать массив под них), потом ввести числа и оно должно мне...

Определить является ли число степенью двойки
Стоит задача Ввести число. Определить является ли оно степенью 2 (число 16 является, а 22 нет)


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

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru