przesunięcie bitowe zamiast znaku dzielenia

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

Nie da się.

A jakoś z wykorzystaniem przesunięcia w lewo? To tylko taka myśl. Też się nie da?

@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 ;]

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

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 :)

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);
        }
    }
}