multiply with add and bitshift only

[bitshifter]

Hi,

wie kann ich ein multiplizier funktion bauen welche intern nur add und bitshift operator verwendet?

LG

[Hyde++ 0]

Schau mal hier:
https://en.wikipedia.org/wiki/Binary_multiplier

[bitshifter]

hi,

habe folgenden code gefunden, kann jemand erklaeren wie er funktioniert?

int mult (int x, int y) {
    if (y == 0)
        return 0;
    else if ((y&1) == 1)
        return x + mult(x<<1, y>>1);
    return mult(x<<1, y>>1);
}

int multiply(int x, int y) {
	if (x < 0 && y < 0) {
		return mult(std::abs(x), std::abs(y));
	} else if (x < 0 || y < 0) {
		return -mult(std::abs(x), std::abs(y));
	}
	return mult(x,y);
}

int main() {
	// your code goes here

	printf("%d, multiply(-12, 33));

	return 0;
}

[bitshifter]

und welche zeitkomplexität hat der code?