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

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

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

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

04.12.2012, 14:30. Просмотров 2452. Ответов 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 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 17:00 #16
Цитата Сообщение от nexen Посмотреть сообщение
В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
Сначала опиши задачу и объясни, где у тебя исходные данные, а где результат. И какое данное где.

Добавлено через 1 минуту
Цитата Сообщение от nexen Посмотреть сообщение
Деление выполняет обычное.
Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.
0
Sanyur
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
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 17:03  [ТС] #18
Sanyur, я думал это и так понятно..
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
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
WhiteP
606 / 204 / 23
Регистрация: 20.11.2012
Сообщений: 426
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
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 17:18 #21
Кстати, в голове всплыло ограничение что число не должно быть отрицательное.
проверьте
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 17:18  [ТС] #22
taras atavin, то ли троль, то ли перепил и залез на форум.. Что тебе в названии темы не понятно? В нём сразу описано и задание, и то, что делить нужно лишь на степень двойки и никаких проверок, соответственно, не нужно производить. Даже если и не понял этого, я уже 3 раза ранее описал задание специально для тебя.

WhiteP, всё-таки есть оптимизация значит.. Сможете восстановить из этого ассемблерного листинга, что же происходит при делении на 2^x и как это написать на высоком уровне? Я в ассемблере соображаю совсем туго :/

Sanyur, насколько я помню, деление с остатком идет только на целые не отрицательные числа, но могу и ошибаться.
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 17:23 #23
Цитата Сообщение от nexen Посмотреть сообщение
taras atavin, то ли троль, то ли перепил и залез на форум
Я вообще не пью.
Цитата Сообщение от nexen Посмотреть сообщение
Что тебе в названии темы не понятно?
А может ты хочешь разделить 90412488 на 8 и от частного взять остаток от деления на 256?

Добавлено через 1 минуту
Цитата Сообщение от Sanyur Посмотреть сообщение
Кстати, в голове всплыло ограничение что число не должно быть отрицательное.
проверьте
Ну вообще да. Отрицательные хранятся в дополнительном коде, где полно нолей на месте единиц.
0
WhiteP
606 / 204 / 23
Регистрация: 20.11.2012
Сообщений: 426
04.12.2012, 17:25 #24
nexen,
C++
1
2
3
4
5
modA = a & (mod-1)
if(a < 0)
{
     modA=((modA--)|(0-mod))++;
}
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 17:43  [ТС] #25
WhiteP, ах вот в чем была загвоздка. Как и сказал Sanyur, а я его не так понял. Спасибо. Вопрос снят.
0
taras atavin
3570 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 20:45 #26
Цитата Сообщение от nexen Посмотреть сообщение
насколько я помню, деление с остатком идет только на целые не отрицательные числа, но могу и ошибаться.
Речь о делимом.
0
04.12.2012, 20:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2012, 20:45
Привет! Вот еще темы с ответами:

Степень двойки и остаток от деления - 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 байт памяти. Почему разработчики выбрали такое странное...


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

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

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