Square-and-Multiply in C

[Dennis S. (eltio)]

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:

#include <stdio.h>
#include <stdint.h>

uint32_t binary_exp( uint32_t x, uint32_t b)
{
    uint32_t res = 1;
    
    for( int i=31; i>=0; --i )
    {
        res = res * res;
        if( (b & (1<<i)) == 1)
        {
            res = res*x;
        }
        printf( "i: %2d \t (1<<i): %2d\n", i, (1<<i) );
    }
    return res;
}

int main( void )
{
    printf( "3 hoch 9: %d", binary_exp( 3U, 9U ) );
    return 0;
}

Und hier die Ausgabe auf der Konsole. Wieso ist das Bit 31 negativ?

i: 31    (1<<i): -2147483648
i: 30    (1<<i): 1073741824
i: 29    (1<<i): 536870912
i: 28    (1<<i): 268435456
i: 27    (1<<i): 134217728
i: 26    (1<<i): 67108864
i: 25    (1<<i): 33554432
i: 24    (1<<i): 16777216
i: 23    (1<<i): 8388608
i: 22    (1<<i): 4194304
i: 21    (1<<i): 2097152
i: 20    (1<<i): 1048576
i: 19    (1<<i): 524288
i: 18    (1<<i): 262144
i: 17    (1<<i): 131072
i: 16    (1<<i): 65536
i: 15    (1<<i): 32768
i: 14    (1<<i): 16384
i: 13    (1<<i): 8192
i: 12    (1<<i): 4096
i: 11    (1<<i): 2048
i: 10    (1<<i): 1024
i:  9    (1<<i): 512
i:  8    (1<<i): 256
i:  7    (1<<i): 128
i:  6    (1<<i): 64
i:  5    (1<<i): 32
i:  4    (1<<i): 16
i:  3    (1<<i):  8
i:  2    (1<<i):  4
i:  1    (1<<i):  2
i:  0    (1<<i):  1
3 hoch 9: 3

Gruß
Dennis

[TriHexagon (Gast)]

Printf interpretiert deine Eingaben als signed integer (%d). Für 
unsigned integer musst du %u verwenden.

https://de.wikibooks.org/wiki/C-Programmierung:_Einfache_Ein-_und_Ausgabe#Formatelemente_von_printf

[Dennis S. (eltio)]

TriHexagon schrieb:
> Printf interpretiert deine Eingaben als signed integer (%d). Für
> unsigned integer musst du %u verwenden.
>
> https://de.wikibooks.org/wiki/C-Programmierung:_Ei...

Oh wie bedauerlich! Daran habe ich nicht gedacht... Vielen Dank!

[Johann L. (gjlayde)]

Dennis S. schrieb:

> ab LSB ist kein Problem

Warum verwendest du nicht die Version ab LSB?  Du brauchst nur Bit 0 des 
Exponenten zu testen und den Exponenten in jedem Durchlauf nach rechts 
zu schieben bis er 0 ist:

#include <stdint.h>

uint32_t binary_exp (uint32_t x, uint32_t b)
{
    uint32_t res = 1;
    
    while (b)
    {
        if (b & 1)
            res *= x;

        x *= x;
        b >>= 1;
    }
    return res;
}

>         if( (b & (1<<i)) == 1)

Für i = 31 ergibt das einen Signed Overflow ergo Undefined Behavior. 
Daher schiebt man für solche Masken niemals 1 sondern immer 1u.

>         if (1 == (b & (1u << i)))

[Dennis S. (eltio)]

Johann L. schrieb:
> Warum verwendest du nicht die Version ab LSB?  Du brauchst nur Bit 0 des
> Exponenten zu testen und den Exponenten in jedem Durchlauf nach rechts
> zu schieben bis er 0 ist:

Das war der erste Schuss der Implementierung und ich habe mir noch keine 
Gedanken gemacht ob es für den Algorithmus egal ist von wo aus ich 
anfange... aber es scheint ja wirklich keine Rolle zu spielen!?

Johann L. schrieb:
> Für i = 31 ergibt das einen Signed Overflow ergo Undefined Behavior.
> Daher schiebt man für solche Masken niemals 1 sondern immer 1u.

Habe ich in meiner Version schon geändert. Übrigens mit einem großen U, 
wie in den MISRA-Regeln empfohlen. ;-)

Gruß
Dennis

[Eric B. (beric)]

Dennis S. schrieb:
> if( (b & (1<<i)) == 1)

b & (1 << i) wird nur 1 wenn i == 0. Das ist nicht was du willst/meinst:

 if (b & (1u << i))

oder

 if ((b & (1u << i)) != 0)

soll funktionieren