Cześć,
Chciałem zapytać jak zrealizować dzielenie przez np. 13 za pomocą przesunięcia bitowego.
Przesuwając w prawo o kolejne liczby, dzielimy przez 2^n, ale jak z tego zrobić 13?
Proszę o wskazówki ;)
Pozdro
- Rejestracja:około 11 lat
- Ostatnio:około 11 lat
- Postów:3
0
A jakoś z wykorzystaniem przesunięcia w lewo? To tylko taka myśl. Też się nie da?
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
2
@gitarowiec997 przesuwanie bitów daje ci mnożenie/dzielenie przez potęgi 2, nic więcej.
Mnożenie przez 13 mógłbyś zrealizować jako:
x16 - x3 = x16 - x4 + x = (x<<4) - (x<<2) +x
ale wątpię żeby było to specjalnie szybsze, a już na pewno nie będzie zbyt czytelne ;]
Ale z dzieleniem już tak łatwo nie jest ;]
edytowany 4x, ostatnio: Shalom
- Rejestracja:około 22 lata
- Ostatnio:ponad rok
2
Jeżeli chcesz to zrobić żeby coś "zoptymalizować" to daj sobie spokój. Kompilator to potrafi, a Ty jak widać nie, więc pozwól mu pracować. GCC robi to tak:
unsigned int x = i / 13;
mov edx, 1321528399 ; 0x4EC4EC4F
mov eax, edx
mul DWORD PTR [rsp+12]
shr edx, 2
edytowany 1x, ostatnio: Endrju
- Rejestracja:około 11 lat
- Ostatnio:około 11 lat
- Postów:3
0
Przed x powinien być plus(na końcu), ale to szczegół.
Shalom napisał(a):
x16 - x3 = x16 - x4 - x = (x<<4) - (x<<2) + x
@Shalom, a to dzielenie jak można by było zrobić?
Do niczego nie jest mi to potrzebne, ale trafiłem gdzieś na takie coś i nie daje mi spokoju :)
- Rejestracja:prawie 20 lat
- Ostatnio:około 13 godzin
0
W http://agner.org/optimize/asmlib.zip są sobie funkcje divfixed* wraz z kodami źródłowymi. Cytuję nagłówek źródeł:
;************************* divfixedi32.asm *********************************
; Author: Agner Fog
; Date created: 2011-07-22
; Last modified: 2011-07-22
;
; Function prototypes:
; void setdivisori32(int buffer[2], int d);
; int dividefixedi32(const int buffer[2], int x);
; void setdivisoru32(uint32_t buffer[2], uint32_t d);
; uint32_t dividefixedu32(const uint32_t buffer[2], uint32_t x);
;
; Description:
; Functions for fast repeated integer division by the same divisor, signed
; and unsigned 32-bit integer versions. The divisor must be positive.
;
; The setdivisor functions calculate the reciprocal divisor and shift counts,
; the dividefixed functions do the division by multiplication and shift.
;
; The methods used are described by:
; T. Granlund and P. L. Montgomery: Division by Invariant Integers Using Multiplication,
; Proceedings of the SIGPLAN 1994 Conference on Programming Language Design and Implementation.
; http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556
;
; Mathematical formula, unsigned division:
; x = dividend
; d = divisor
; n = integer size, bits
; L = ceil(log2(d))
; m = 1 + 2^n * (2^L-d) / d [2^L should overflow to 0 if L = n]
; sh1 = min(L,1)
; sh2 = max(L-1,0)
; t = m*x >> n [high part of unsigned multiplication]
; x/d = (((x-t) >> sh1) + t) >> sh2
;
; Mathematical formula, signed division:
; x = dividend
; d = abs(divisor)
; n = integer size, bits
; L = ceil(log2(d))
; L = max(L,1)
; m = 1 + 2^(n+L-1)/d - 2^n [division should overflow to 0 if d = 1]
; sh1 = L-1
; q = x + (m*x >> n) [high part of signed multiplication]
; q = (q >> sh1) - (x<0 ? -1 : 0)
; if (divisor < 0) q = -q [negative divisor not supported in present implementation]
; x/d = q
;
; Copyright (c) 2011 GNU General Public License www.gnu.org/licenses
;******************************************************************************
Dzielenie przez 13 za pomocą przesunięć bitowych ciężko zrobić z dobrą precyzją, ale możesz to chyba dość dobrze przybliżyć. 1/13 binarnie to:
WolframAlpha napisał(a)
0.000100111011000100111011000100111..._2
Obcinając trochę cyfr dostajemy: 0.000100111011 i z tego możemy sklepać kod, np:
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random r = new Random();
for (int i = 0; i < 10; i++) {
int x = r.nextInt(1234567);
int normalResult = x / 13;
int estimatedResult = (x >> 4) + (x >> 6) - (x >> 9) + (x >> 11)
+ (x >> 12);
System.out.println(x + " " + normalResult + " " + estimatedResult);
}
}
}
Albo jeszcze lepiej:
import java.util.Random;
public class Main {
public static void main(String[] args) {
Random r = new Random();
for (int i = 0; i < 10; i++) {
int x = r.nextInt(1234567);
int normalResult = x / 13;
int estimatedResult = (x >> 4) + (x >> 6) - (x >> 9) + (x >> 11)
+ (x >> 12) + (x >> 16) + (x >> 18) - (x >> 21);
System.out.println(x + " " + normalResult + " " + estimatedResult);
}
}
}
edytowany 3x, ostatnio: Wibowit
x*16 - x*4 + x- sam x musi być z plusem, w dwóch miejscachShalom