Hallo zusammen,
ich möchte den Square-and-Multiply-Algorithmus in C implementieren.
Allerdings habe ich schon einen Fehler bei dem "Durchlaufen" der
einzelnen Bits des Exponenten ab dem MSB (ab LSB ist kein Problem). Hier
ist der Code:
1 | #include <stdio.h>
|
2 | #include <stdint.h>
|
3 |
|
4 | uint32_t binary_exp( uint32_t x, uint32_t b)
|
5 | {
|
6 | uint32_t res = 1;
|
7 |
|
8 | for( int i=31; i>=0; --i )
|
9 | {
|
10 | res = res * res;
|
11 | if( (b & (1<<i)) == 1)
|
12 | {
|
13 | res = res*x;
|
14 | }
|
15 | printf( "i: %2d \t (1<<i): %2d\n", i, (1<<i) );
|
16 | }
|
17 | return res;
|
18 | }
|
19 |
|
20 | int main( void )
|
21 | {
|
22 | printf( "3 hoch 9: %d", binary_exp( 3U, 9U ) );
|
23 | return 0;
|
24 | }
|
Und hier die Ausgabe auf der Konsole. Wieso ist das Bit 31 negativ?
1 | i: 31 (1<<i): -2147483648
|
2 | i: 30 (1<<i): 1073741824
|
3 | i: 29 (1<<i): 536870912
|
4 | i: 28 (1<<i): 268435456
|
5 | i: 27 (1<<i): 134217728
|
6 | i: 26 (1<<i): 67108864
|
7 | i: 25 (1<<i): 33554432
|
8 | i: 24 (1<<i): 16777216
|
9 | i: 23 (1<<i): 8388608
|
10 | i: 22 (1<<i): 4194304
|
11 | i: 21 (1<<i): 2097152
|
12 | i: 20 (1<<i): 1048576
|
13 | i: 19 (1<<i): 524288
|
14 | i: 18 (1<<i): 262144
|
15 | i: 17 (1<<i): 131072
|
16 | i: 16 (1<<i): 65536
|
17 | i: 15 (1<<i): 32768
|
18 | i: 14 (1<<i): 16384
|
19 | i: 13 (1<<i): 8192
|
20 | i: 12 (1<<i): 4096
|
21 | i: 11 (1<<i): 2048
|
22 | i: 10 (1<<i): 1024
|
23 | i: 9 (1<<i): 512
|
24 | i: 8 (1<<i): 256
|
25 | i: 7 (1<<i): 128
|
26 | i: 6 (1<<i): 64
|
27 | i: 5 (1<<i): 32
|
28 | i: 4 (1<<i): 16
|
29 | i: 3 (1<<i): 8
|
30 | i: 2 (1<<i): 4
|
31 | i: 1 (1<<i): 2
|
32 | i: 0 (1<<i): 1
|
33 | 3 hoch 9: 3
|
Gruß
Dennis
