Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: O metodă foarte ciudată de a calcula puterile lui 2 modulo 2 10^9+7  (Citit de 1114 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
antoniu200
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« : Februarie 08, 2019, 13:10:52 »

Am găsit în rezolvarea unei probleme acest subprogram care calculează 2^n modulo 10^9+7.

Cod:
const unsigned long long mod = 1000000007;
unsigned long long mul (long long a, long long b)
{
    return (a * b) % mod;
};
unsigned long long pw (long base, long exponent)
{
    int result = 1;
    for (int bit=0;(1 << bit) <= exponent; bit++)
    {
        if (exponent & (1 << bit))
        {
            result = mul (result, base);
        }
        base = mul (base, base);
    }
    return result;
};

Îmi poate cineva explica, vă rog, când condiția
Cod:
exponent & (1 << bit)
se evaluează la un număr diferit de 0? Știu că & este conjuncție pe biți, dar asta nu mă lămurește.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines