e305: Xor 運算
Tags : bit manipulation
Accepted rate : 47人/50人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-06 08:42

Content

有一個函式如下

C/C++:

  1. long long sumxor(long long N){
  2. long long ans=0;
  3. for(long long i=0;i<N;i++){
  4. if((N^i)==(N+i))ans++;
  5. }
  6. return ans;
  7. } 

Python:

  1. def sumxor(N):
  2. ans=0
  3. for i in range(N):
  4. if((N^i)==(N+i)):
  5. ans+=1
  6. return ans

Java(感謝rexwu1104@gmail.com 提供):

  1. public static long sumxor(long N){
  2. long ans=0;
  3. for (long i=0;i<N;i++) {
  4. if ((N^i)==(N+i)) ans++;
  5. }
  6. return ans;
  7. }

pascal(感謝rexwu1104@gmail.com 提供):

  1. var
  2.     i, N: int64;
  3.     ans : int64 = 0;
  4. function sumxor(N: int64):int64;
  5. begin
  6.     ans:=0;
  7.     for i := 0 to N do begin
  8.         if ((xor i) = (+ i)) then ans:=ans+1;
  9.         if (N=0) ans:=0;
  10.         sumxor:=ans;
  11.     end;
  12. end;

因為要處理的N很大,現在請你優化這個函式

Input

多筆測資

一行有一個整數N(N<1015)

Output

輸出函式的回傳值

Sample Input
4
10
Sample Output
4
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 0.1s , <1M
公開 測資點#1 (50%): 0.1s , <1M
Hint :
  • 測資#0:N< 1015 ,約 104 筆測資
  • 測資#1:N< 215 ,約 103 筆測資

感謝icube大大提醒,已修正錯誤

Tags:
bit manipulation
出處:
π [管理者:
314159265358979... (少年π)
]


ID User Problem Subject Hit Post Date
18348
vincent97198 (學測戰士)
e305
解法和原理
257 2019-07-05 17:53