如何正确地进行 GMP 位移位？

Question

我需要使用高精度整数进行一些计算，并且想使用 GMP 库。我希望这里有人对此有经验，因为我不明白如何使用移位。我正在尝试使用下面的代码。代码编译但 b 仍然包含 0.

https://gmplib.org/manual/Low_002dlevel-Functions

#include <stdio.h>                                                                                                                                                                                                                           
#include <gmp.h>                                                                                                                                                                                                                             
                                                                                                                                                                                                                                             
int main()                                                                                                                                                                                                                                   
{                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                             
    mpz_t a;                                                                                                                                                                                                                                 
    mpz_t b;                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mpz_init2(b, a->_mp_size);                                                                                                                                                                                                               
    mpz_set_str(a, "1", 16);                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mp_limb_t bits = mpn_lshift(b->_mp_d, &a->_mp_d[0], a->_mp_size, 1);                                                                                                                                                                     
                                                                                                                                                                                                                                             
    gmp_printf("%Zx\n", a);                                                                                                                                                                                                                  
    gmp_printf("Bits shifted %M\n", bits);                                                                                                                                                                                                   
    gmp_printf("%Zd", b);                                                                                                                                                                                                                    
                                                                                                                                                                                                                                             
    return 0;                                                                                                                                                                                                                                
}

Answer 1

下面的代码使用 mpz_fdiv_q_2exp 进行右移，mpz_mul_2exp 进行左移以及 mpz_tdiv_r_2exp。 mpz_tdiv_r_2exp 是必需的，因为当数据成倍增加时大小会增加。

#include <stdio.h>                                                                                                                                                                                                                           
#include <gmp.h>                                                                                                                                                                                                                             
                                 

int main()                                                                                                                                                                                                                                   
{                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                             
    mpz_t a;                                                                                                                                                                                                                                 
    mpz_t b;                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                             
    mpz_init_set_str(a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16);                                                                                                                                                                                  
              
    for ( int i = 0; i < 128;  i++) {
        
        //left shift
        mpz_mul_2exp(b,a,I);
        //This is faster than `mpz_mod` since we are in 2^128 
        mpz_tdiv_r_2exp(b,b,128);
        
        //right shift
        //mpz_fdiv_q_2exp( b,a,i);     
    
        gmp_printf("\n%#40Zx", b); 
    }
    
    gmp_printf("\n%Zd", a);
    
    return 0;                                                                                                                                                                                                                                
}

部分输出

      0xffffffffffffffffffffffffffffffff
      0xfffffffffffffffffffffffffffffffe
      0xfffffffffffffffffffffffffffffffc
      ...
      0xe0000000000000000000000000000000
      0xc0000000000000000000000000000000
      0x80000000000000000000000000000000

GMP manual page 35

For positive n both mpz_fdiv_q_2exp and mpz_tdiv_q_2exp are simple bitwise right shifts.

注意：可以直接使用mpn_lshift和mpn_rshift，但是需要在开发库下进行更多的编码和测试。具体如何复杂可以看mpz_mul_2exp的源码

如何正确地进行 GMP 位移位？

How to properly do a GMP bit shift?

c

gmp