二進制表示中一個數字在奇數和偶數位置的數目是多少？

他們是實現它的任何更快的方法，無論它是64位的整數範圍還是任何函數。除了我已經實現的一個。二進制表示中一個數字在奇數和偶數位置的數目是多少？

/* 
Find F(i)=abs(a(i)-b(i)) 
a(i)=number of 1's in even position 
b(i)=number of 1's in odd position 
for an integer i, where i fits in 64-bit 
*/ 
//function calculate the above equation 
//returns the answer 
long long int F(long long int k) 
{ 
    //size of array is taken for 64-bit number 
    int a[64]={0},i,a,b; 
    long long int m; 
    m=k; 
    //convert long long int into binary 
    for(i=63;i>-1;i--) 
    { 
     if(m==1||m==0) 
     { 
      a[i]=m; 
      break;  //exit the for loop 
     } 
     a[i]=m%2;  //storing bit by bit 
     m/=2;   
    } 
    // initialized with a value of zero 
    a=0; 
    b=0; 
    //find first bit having 1 
    int f; 
    for(i=0;i<64;i++) 
    { 
     if(a[i]==1) 
     { 
      f=i; 
      break; 
     } 
    } 
    //calculating the number of 1's in even and odd positions 
    for(i=f;i<64;i++) 
    { 
     if(a[i]==1) 
     { 
      if((63-f)%2==0) 
      { 
       a++;   //1's in even positions 
      } 
      else 
      { 
       b++;   //1's in odd positions 
      } 
     } 
    } 

    //return the answer 
    return abs(a-b); 
}

所以基本上我所要做的是通過簡單的方法將整數轉換在其二進制表示使用MOD 2.然後，執行任務找到的第1的二進制表示爲從左到右我們的指針在第一個數字上。現在使用前1的索引計算奇數和偶數位置1的數目。最後返回總和偶數和奇數位置1的絕對差值。

來源

2014-09-12 Vistanza

一個爲你的網站：https://graphics.stanford.edu/~seander/bithacks.html – Deduplicator 2014-09-12 18:47:32

對於快速實現使用二進制移位操作。 – 2014-09-12 18:58:02

@Learner：這可能會更快一些，但bithacks頁面仍然列出了更好的選項。 – Deduplicator 2014-09-12 19:01:56

一個簡單的方法：

#include <stdint.h> 
int absdiffevenoddpopcount(uint64_t x) { 
    uint64_t a = x & 0x5555555555555555; 
    uint64_t b = x & ~0x5555555555555555; 
    while(a && b) { 
     a &= a - 1; 
     b &= b - 1; 
    } 
    x = a ? a : b; 
    int r = 0; 
    while(x) { 
     x &= x - 1; 
     r++; 
    } 
    return r; 
}

反正這個頁面收集此類位黑客：https://graphics.stanford.edu/~seander/bithacks.html

此外，一些處理器有可能是（比特）人口計數更快特殊說明，通常編譯器會將它作爲內置函數提供給C.

來源

2014-09-12 18:58:27 Deduplicator

666口罩從哪裏來？ – harold 2014-09-12 19:05:36

@harold：錯誤的面具，sry。 – Deduplicator 2014-09-12 19:10:17

請注意，對於性能來說，使用內建的popcount可能會更好，因爲它可能會映射到一條CPU指令。例如在英特爾，自Nehalem以來就有這樣的指令。 – kipodi 2014-09-12 19:29:46

基本上你可以做的是使用&只留下奇數和偶數位。你可以對兩個數字都進行計數，最後返回差異。所以：

long long int F(long long int k) 
{ 
    long long int odds, evens; 
    odds = k & 0x5555555555555555; 
    evens = k & 0xaaaaaaaaaaaaaaaa; 
    return abs(__builtin_popcountll(odds) - __builtin_popcountll(evens)); 
}

我寫的用gcc bultin popcount。如果使用其他編譯器，您可以在其手冊中找到它。

來源

2014-09-12 19:01:38 kipodi

爲什麼你將結果擴大到「長久」？ popcount返回'int'，它有很多範圍，甚至很長的'long long'。 – 2014-09-12 19:13:27

我拿了他原來的功能簽名，也許他需要很長時間才能找到別的東西。 – kipodi 2014-09-12 19:25:58

更C++友好的版本：

int F(long long const k) { 
    return std::abs(static_cast<int>(std::bitset<64>(k & 0x5555555555555555).count()) - 
        static_cast<int>(std::bitset<64>(k & 0xaaaaaaaaaaaaaaaa).count())); 
}

LIVE DEMO

來源

2014-09-12 19:18:38 101010

二進制表示中一個數字在奇數和偶數位置的數目是多少？

回答

相關問題