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

@nexen · Регистрация: 27.01.2012

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

Раньше я всегда использовал примерной такой подход :

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. Я бы использовал этот подход, но кто-то как-то сказал мне, что такое решение в каких-то случаях выдает не верный результат или ошибки. Я напрочь забыл, кто это сказал :/
Вопрос : в чем плох такой подход и как правильно?
Скорее всего, компиляторы сами производят подобную оптимизацию, но всё же.

@taras atavin · 04.12.2012, 15:29

А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?

@nexen · 04.12.2012, 15:48 **[ТС]**

Сообщение от taras atavin

А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?

Издеваетесь что ли?..

@taras atavin · 04.12.2012, 16:07

Издеваешься здесь ты.

@nexen · 04.12.2012, 16:13 **[ТС]**

Сообщение от taras atavin

Издеваешься здесь ты.

Где же? Что не понятного то? Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю. Я привел листинг, как это делал я раньше. Некто сказал мне, что такой подход не верен в некоторых случаях. Я задал вопрос, когда этот листинг может быть не верен и почему, а так же попросил привести верный листинг.
А теперь новый вопрос : где здесь издевательство? Что здесь не понятно?.. Ей богу, только настроение испортили.

@taras atavin · 04.12.2012, 16:15

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

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

И где у тебя сдвиги? Кроме того, что на что ты собирался делить, где у тебя результат и при чём здесь вообще типы из твоего поста не понятно.

WhiteP · 04.12.2012, 16:31

Я так понимаю речь о взятии остатка от деления на степень двойки (деление по модулю).
Чем не устраивает modA = a % mod?

@nexen · 04.12.2012, 16:38 **[ТС]**

WhiteP, % выполняет обычное деление по сути. Так как модуль в данном случае степень двойки, то можно написать более быстрое модульное деление. Поэтому и не устраивает обычный %. Но, как я написал, компиляторы, наверное, справляются с этим. Только как..

WhiteP · 04.12.2012, 16:48

Написал тестовый пример.

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

Так что компилятор тут все "дословно" скомпилил. Ну это он не знает, что степень двойки, естессно.

@taras atavin · 04.12.2012, 16:54

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

WhiteP, % выполняет обычное деление по сути.

Бред. % вычисляет остаток.

WhiteP · 04.12.2012, 16:56

taras atavin,
на уровне ассемблера производится деление (idiv) при котором в одном регистре - частное, а в другом остаток.
Когда нам нужно частное - выдается один регистр, а когда остаток - другой. Операция же одна и та же.

@nexen · 04.12.2012, 16:57 **[ТС]**

WhiteP, хм, сам не проверял, лишь слышал, что компиляторы давно уже научились a*16, b/32 и c%256 заменять на быстрые эквиваленты. То ли с модулем всё не так, то ли врали мне ;/
И всё же вопрос остался. В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?

@Sanyur · 04.12.2012, 16:57

Ваш код тоже вычисляет остаток деления от степени двойки

@taras atavin · 04.12.2012, 16:58

Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.

@nexen · 04.12.2012, 16:59 **[ТС]**

Сообщение от taras atavin

Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.

И что? Деление выполняет обычное.

@taras atavin · 04.12.2012, 17:00

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

В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?

Сначала опиши задачу и объясни, где у тебя исходные данные, а где результат. И какое данное где.

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

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

Деление выполняет обычное.

Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.

@Sanyur · 04.12.2012, 17:01

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

@nexen · 04.12.2012, 17:03 **[ТС]**

Sanyur, я думал это и так понятно..

@taras atavin · 04.12.2012, 17:04

Будет глючить в том случае, если 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, чтоб ещё больше съэкономить: целочисленное вычитание, как и целочисленное сложение хоть и быстрей деления, но всё таки не бесконечно быстрей.

WhiteP · 04.12.2012, 17:10

Сообщение от 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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	04.12.2012, 15:29
	А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал? 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	04.12.2012, 16:07
	Издеваешься здесь ты. 1

WhiteP 840 / 347 / 67 Регистрация: 20.11.2012 Сообщений: 809
	04.12.2012, 16:31
	Я так понимаю речь о взятии остатка от деления на степень двойки (деление по модулю). Чем не устраивает modA = a % mod? 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	04.12.2012, 16:38 [ТС]
	WhiteP, % выполняет обычное деление по сути. Так как модуль в данном случае степень двойки, то можно написать более быстрое модульное деление. Поэтому и не устраивает обычный %. Но, как я написал, компиляторы, наверное, справляются с этим. Только как.. 0

WhiteP 840 / 347 / 67 Регистрация: 20.11.2012 Сообщений: 809
	04.12.2012, 16:56
	taras atavin, на уровне ассемблера производится деление (idiv) при котором в одном регистре - частное, а в другом остаток. Когда нам нужно частное - выдается один регистр, а когда остаток - другой. Операция же одна и та же. 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	04.12.2012, 16:57 [ТС]
	WhiteP, хм, сам не проверял, лишь слышал, что компиляторы давно уже научились a*16, b/32 и c%256 заменять на быстрые эквиваленты. То ли с модулем всё не так, то ли врали мне ;/ И всё же вопрос остался. В каких случаях листинг из первого сообщения выдает не правильный результат и как надо? 0

@Sanyur 11 / 11 / 0 Регистрация: 19.03.2010 Сообщений: 101
	04.12.2012, 16:57
	Ваш код тоже вычисляет остаток деления от степени двойки 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	04.12.2012, 16:58
	Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток. 0

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	04.12.2012, 17:03 [ТС]
	Sanyur, я думал это и так понятно.. 0