Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день Заказать работу  
 
1 из 2 1 2 »
 
Рейтинг 4.93/40: Рейтинг темы: голосов - 40, средняя оценка - 4.93
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
1

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

04.12.2012, 14:30. Показов 7299. Ответов 25
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Раньше я всегда использовал примерной такой подход :
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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 04.12.2012, 14:30
Ответы с готовыми решениями:

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

степень двойки
Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе. int a,b=1; ...

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

Точная степень двойки
Написал прогу. Как сделать, чтобы при вводе числа не являющейся точной степенью двойки, прога не...

25
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 15:29 2
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 15:48  [ТС] 3
Цитата Сообщение от taras atavin Посмотреть сообщение
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
Издеваетесь что ли?..
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 16:07 4
Издеваешься здесь ты.
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:13  [ТС] 5
Цитата Сообщение от taras atavin Посмотреть сообщение
Издеваешься здесь ты.
Где же? Что не понятного то? Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю. Я привел листинг, как это делал я раньше. Некто сказал мне, что такой подход не верен в некоторых случаях. Я задал вопрос, когда этот листинг может быть не верен и почему, а так же попросил привести верный листинг.
А теперь новый вопрос : где здесь издевательство? Что здесь не понятно?.. Ей богу, только настроение испортили.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 16:15 6
Цитата Сообщение от nexen Посмотреть сообщение
Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю.
И где у тебя сдвиги? Кроме того, что на что ты собирался делить, где у тебя результат и при чём здесь вообще типы из твоего поста не понятно.
0
836 / 343 / 67
Регистрация: 20.11.2012
Сообщений: 795
04.12.2012, 16:31 7
Я так понимаю речь о взятии остатка от деления на степень двойки (деление по модулю).
Чем не устраивает modA = a % mod?
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:38  [ТС] 8
WhiteP, % выполняет обычное деление по сути. Так как модуль в данном случае степень двойки, то можно написать более быстрое модульное деление. Поэтому и не устраивает обычный %. Но, как я написал, компиляторы, наверное, справляются с этим. Только как..
0
836 / 343 / 67
Регистрация: 20.11.2012
Сообщений: 795
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
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 16:54 10
Цитата Сообщение от nexen Посмотреть сообщение
WhiteP, % выполняет обычное деление по сути.
Бред. % вычисляет остаток.
0
836 / 343 / 67
Регистрация: 20.11.2012
Сообщений: 795
04.12.2012, 16:56 11
taras atavin,
на уровне ассемблера производится деление (idiv) при котором в одном регистре - частное, а в другом остаток.
Когда нам нужно частное - выдается один регистр, а когда остаток - другой. Операция же одна и та же.
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:57  [ТС] 12
WhiteP, хм, сам не проверял, лишь слышал, что компиляторы давно уже научились a*16, b/32 и c%256 заменять на быстрые эквиваленты. То ли с модулем всё не так, то ли врали мне ;/
И всё же вопрос остался. В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
0
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 16:57 13
Ваш код тоже вычисляет остаток деления от степени двойки
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 16:58 14
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:59  [ТС] 15
Цитата Сообщение от taras atavin Посмотреть сообщение
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
И что? Деление выполняет обычное.
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 17:00 16
Цитата Сообщение от nexen Посмотреть сообщение
В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
Сначала опиши задачу и объясни, где у тебя исходные данные, а где результат. И какое данное где.

Добавлено через 1 минуту
Цитата Сообщение от nexen Посмотреть сообщение
Деление выполняет обычное.
Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.
0
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 17:01 17
C++
1
2
3
4
5
6

int mod = 8;//делим на 8
int a = 90412488;//что делим на 8
char b = 113;//тожесамое
int modA, modB;// остатки от деления на 8
modA = a & int(mod-1);
modB = b & char(mod-1);
Для наглядности:
a=20(10100)
делим на 16
mod=16(1000)
1000-1= 0111
получаем 10100
& 00111
_____
00100 = 4
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 17:03  [ТС] 18
Sanyur, я думал это и так понятно..
0
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
04.12.2012, 17:04 19
Будет глючить в том случае, если mod не равно целой степени двойки, если же делать проверку, то на ней потеряешь ещё больше. Вывод: применять только в тех случаях, когда априорно известно, что делитель равен целой степени двойки. И можно даже так:
C++
1
2
3
4
5
6

int mod = 8;//делим на 8
int a = 90412488;//что делим на 8
char b = 113;..тожесамое
int modA, modB;// остатки от деления на 8
modA = a & (mod-1);
modB = b & (mod-1);
. Если mod - константа, то лучше заранее вычислить mod-1, чтоб ещё больше съэкономить: целочисленное вычитание, как и целочисленное сложение хоть и быстрей деления, но всё таки не бесконечно быстрей.
0
836 / 343 / 67
Регистрация: 20.11.2012
Сообщений: 795
04.12.2012, 17:10 20
Цитата Сообщение от taras atavin Посмотреть сообщение
Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.
Просто операция деления одна из самых затратных по времени (на уровне тактов, конечно)

Добавлено через 4 минуты
Если константой заменить (a % 8), то вот так оптимизирует.

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

?mod1@@YAHH@Z PROC                  ; mod1, COMDAT
; _a$ = ecx
 
; 6    :    return a % 8;
 
    and ecx, -2147483641            ; 80000007H
    jns SHORT $LN3@mod1
    dec ecx
    or  ecx, -8                 ; fffffff8H
    inc ecx
$LN3@mod1:
    mov eax, ecx
 
; 7    : }
 
    ret 0
?mod1@@YAHH@Z ENDP
1
04.12.2012, 17:10
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 04.12.2012, 17:10
Помогаю со студенческими работами здесь

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

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

Найти степень двойки
Дано целое число N&gt;0, являющееся некоторой степенью числа 2:N=2 ^k. Найти целое число К -...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru