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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

04.12.2012, 14:30. Просмотров 2482. Ответов 25
Метки нет (Все метки)

Раньше я всегда использовал примерной такой подход :
C++
1
2
3
4
5
6
int mod = 8;
int a = 90412488;
char b = 113;
int modA, modB;
modA = a & int(mod-1);
modB = b & char(mod-1);
Понятное дело, что можно написать функцию, которая определала бы тип и была бы красивой оберткой для такого подхода, но мне хватало. Сейчас встал опять вопрос с модульным делением на 2^x. Я бы использовал этот подход, но кто-то как-то сказал мне, что такое решение в каких-то случаях выдает не верный результат или ошибки. Я напрочь забыл, кто это сказал :/
Вопрос : в чем плох такой подход и как правильно?
Скорее всего, компиляторы сами производят подобную оптимизацию, но всё же.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.12.2012, 14:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Модульное деление на степень двойки (C++):

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

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

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

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

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

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

25
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
04.12.2012, 15:29 #2
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 15:48  [ТС] #3
Цитата Сообщение от taras atavin Посмотреть сообщение
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
Издеваетесь что ли?..
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
04.12.2012, 16:07 #4
Издеваешься здесь ты.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:13  [ТС] #5
Цитата Сообщение от taras atavin Посмотреть сообщение
Издеваешься здесь ты.
Где же? Что не понятного то? Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю. Я привел листинг, как это делал я раньше. Некто сказал мне, что такой подход не верен в некоторых случаях. Я задал вопрос, когда этот листинг может быть не верен и почему, а так же попросил привести верный листинг.
А теперь новый вопрос : где здесь издевательство? Что здесь не понятно?.. Ей богу, только настроение испортили.
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
04.12.2012, 16:15 #6
Цитата Сообщение от nexen Посмотреть сообщение
Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю.
И где у тебя сдвиги? Кроме того, что на что ты собирался делить, где у тебя результат и при чём здесь вообще типы из твоего поста не понятно.
0
WhiteP
606 / 204 / 23
Регистрация: 20.11.2012
Сообщений: 426
04.12.2012, 16:31 #7
Я так понимаю речь о взятии остатка от деления на степень двойки (деление по модулю).
Чем не устраивает modA = a % mod?
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:38  [ТС] #8
WhiteP, % выполняет обычное деление по сути. Так как модуль в данном случае степень двойки, то можно написать более быстрое модульное деление. Поэтому и не устраивает обычный %. Но, как я написал, компиляторы, наверное, справляются с этим. Только как..
0
WhiteP
606 / 204 / 23
Регистрация: 20.11.2012
Сообщений: 426
04.12.2012, 16:48 #9
Написал тестовый пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int mod1(int a, int mod)
{
    return a % mod;
}
 
int mod2(int a, int mod)
{
    return a & int(mod-1);
}
 
int main()
{
    int a=0, mod = 0;
    cout<<"Enter a: " ;cin>>a;
    cout<<"Enter mod: "; cin>>mod;
    cout<<"\n"<<mod1(a, mod)<<"\n";
    cout<<"\n"<<mod2(a, mod)<<"\n";
    return 0;
}
Откомпилировал студийным (VS 2012) компилятором с ключом оптимизации /O2 (Maximize speed).

Результат:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
?mod1@@YAHHH@Z PROC                 ; mod1, COMDAT
; _a$ = ecx
; _mod$ = edx
 
; 5    : {
 
    push    esi
    mov esi, edx
 
; 6    :    return a % mod;
 
    mov eax, ecx
    cdq
    idiv    esi
    pop esi
    mov eax, edx
 
; 7    : }
 
    ret 0
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
?mod2@@YAHHH@Z PROC                 ; mod2, COMDAT
; _a$ = ecx
; _mod$ = edx
 
; 11   :    return a & int(mod-1);
 
    lea eax, DWORD PTR [edx-1]
    and eax, ecx
 
; 12   : }
 
    ret 0
?mod2@@YAHHH@Z ENDP
Так что компилятор тут все "дословно" скомпилил. Ну это он не знает, что степень двойки, естессно.
1
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
04.12.2012, 16:54 #10
Цитата Сообщение от nexen Посмотреть сообщение
WhiteP, % выполняет обычное деление по сути.
Бред. % вычисляет остаток.
0
WhiteP
606 / 204 / 23
Регистрация: 20.11.2012
Сообщений: 426
04.12.2012, 16:56 #11
taras atavin,
на уровне ассемблера производится деление (idiv) при котором в одном регистре - частное, а в другом остаток.
Когда нам нужно частное - выдается один регистр, а когда остаток - другой. Операция же одна и та же.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:57  [ТС] #12
WhiteP, хм, сам не проверял, лишь слышал, что компиляторы давно уже научились a*16, b/32 и c%256 заменять на быстрые эквиваленты. То ли с модулем всё не так, то ли врали мне ;/
И всё же вопрос остался. В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
0
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 16:57 #13
Ваш код тоже вычисляет остаток деления от степени двойки
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
04.12.2012, 16:58 #14
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:59  [ТС] #15
Цитата Сообщение от taras atavin Посмотреть сообщение
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
И что? Деление выполняет обычное.
0
04.12.2012, 16:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2012, 16:59
Привет! Вот еще темы с ответами:

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

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

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

Степень двойки для отражения размера памяти - C++
Коллеги глупый но все же интересный вопрос! Один гибибайт состоит из 1073741824 байт памяти. Почему разработчики выбрали такое странное...


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

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

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