obtenir les 32 bits élevés de multiplier deux entiers non signés (HW)

Question

Je lis CSAPP et j'essaie de répondre aux questions de devoirs. Supposons que w = 32, 2,75 consiste à obtenir les 32 bits élevés de multiplier deux entiers non signés de 32 bits. Étant donné la fonction int signed_high_prod(int x, int y) qui calcule les 32 bits de poids fort de x. y pour le cas où x et y sont sous forme de complément à deux. int signed_high_prod(int x, int y) doit être utilisé pour implémenter unsigned int unsigned_high_prod(unsigned x, unsigned y). Par google, j'ai trouvé x'.y' = x.y + x.y_31.2^32 + y.x_31.2^32 + x_31.y_31.2^64, où x 'et y' sont des formes non signées de x et y respectivement.

Je n'arrive toujours pas à comprendre la réponse.

unsigned unsigned_high_prod(unsigned x, unsigned y){ 
    unsigned p = (unsigned) signed_high_prod((int) x, (int) y) 
    if((int) x < 0){ 
     p += y; 
    } 
    if((int) y < 0){ 
     p += x; 
    } 
    return p; 
} 

Pourquoi le terme final n'a aucun effet sur le résultat? pourquoi quand x < 0 donc x_31 = 1, plus y? et la même chose avec y.

Answer 1

Pour convertir un entier signé 32 bits à un entier 32 bits non signé, nous ajoutons 2³² à sa valeur s'il est négatif.

signed_high_prod effectue une multiplication signée et renvoie les bits 63 à 32 du produit. Nous voulons unsigned_high_prod faire la même chose pour la multiplication non signée et faire usage de signed_high_prod et ensuite compenser la différence entre la multiplication non signée et signée.

Let N(i) = { 1, i < 0 
      { 0, i >= 0 

Let U(i) = i + N(i)·2³² { −2³¹ <= i < 2³¹ } 

Puis:

U(x)·U(y) = (x + N(x)·2³²)·(y + N(y)·2³²) 
      = x·y + x·N(y)·2³² + N(x)·2³²·y + N(x)·2³²·N(y)·2³² 
      = x·y + x·N(y)·2³² + y·N(x)·2³² + N(x)·N(y)·2⁶⁴ 

⌊U(x)·U(y)/2³²⌋ = ⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³² 

Depuis l'arithmétique sur nombres entiers non signés 32 bits sera effectuée modulo 2³², nous avons:

⌊U(x)·U(y)/2³²⌋ mod 2³² = (⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³²) mod 2³² 
         = (⌊x·y/2³²⌋ + x·N(y) + y·N(x)) mod 2³² 

Je crois que les comptes pour les calculs effectués par votre unsigned_high_prod fonction.

Answer 2

Pour effectuer une multiplication au niveau des bits, nous devons d'abord étendre les bits, puis passer par une série de décalages et d'additions. Par exemple, en supposant w = 3, laissez x = [011] et y = [101]. (C.-à-x = 3 et y = -3 (signed) or 5 (unsigned))

Pour effectuer le produit non signé, nous première adressons zéro comme suit: (en ignorant les bits 6 et au-dessus)

 000 011 
    * 000 101 
    -------- 
    000 011 
    + 001 100 
    -------- 
    001 111 
    ======== 

Par conséquent, les bits d'ordre élevé non signés sont [001]

Pour effectuer le produit signé, nous avons d'abord d'extension de signe comme suit:

 000 011 
    * 111 101 
    -------- 
    000 011 
    + 001 100 
    + 011 000 ** 
    + 110 000 ** 
    + 100 000 ** 
    -------- 
    110 111 
    ======== 

Par conséquent, le signe Notez que la différence entre les bits de poids fort signés et non signés (comme indiqué par ** ci-dessus) est que nous avons ajouté [111] * [011] dans le cas signé. Par conséquent, nous devons soustraire ce montant pour obtenir les bits de poids fort non signés.

The unsigned high order bits = [110] - [111] * [011] 
          = [110] - [101] 
          = [110] + [011] ?? 
          = [001] (as above) 

Parce que [111] = -1, la quantité de correction, - [111] * [011] équivaut à - (-1 * x) = x.Par conséquent, lorsque y est négatif (comme dans ce cas), nous devons corriger le résultat en ajoutant x. Simultanément, lorsque x est négatif, nous devons corriger le résultat en ajoutant y.

?? -[101] = ~[101] + 1 = [010] + [001] = [011]