用有限的位数找到最大的奇数

Question

我试图解决这个问题，但自动法官返回“超过时限”（TLE）。

情人节之际，亚当和夏娃继续参加比赛。他们通过了所有的回合，进入了决赛。在最后一轮中，亚当得到一个偶数N和一个整数K，他必须找到最大的奇数M小于N，使得M的二进制表示中的数字之和最大为K。

输入格式：

对于每个测试用例，您都会得到一个偶数N和一个整数K

输出格式：

对于每个测试用例，输出整数M（如果存在），否则打印-1

限制条件：

>

1≤T≤10⁴

2.≤ N≤ 10⁹

0≤K≤30

示例输入：

2  
10 2  
6 1 

样本输出：

9 
1

这是我到目前为止所做的。

    static long play(long n, int k){
      if(k==0) return -1;
      if(k==1) return 1;
      long m=n-1;      
      while(m>0){                      
              long value=Long.bitCount(m); //built in function to count bits
              if(value<=k ){                  
                  return m;
              }
              m=m-2;          
      }     
        return -1;
    }

    public void solve(InputReader in, OutputWriter out) {
       long start=System.currentTimeMillis(); 
       int t=in.readInt();
       while(t-->0){                
          long n=in.readLong();         
          int k=in.readInt();
          long result=play(n,k);         
          out.printLine(result);
       }
       long end=System.currentTimeMillis();
       out.printLine((end-start)/1000d+"ms");       
    } 
 }       

Answer 1

因为答案很奇怪，

让ans=1，这里我们使用1位，所以k=k-1；

现在ans的二进制表示是

ans(binary) = 00000000000000000000000000000001

while(k > 0):

     make 30th position set
     ans(binary) = 01000000000000000000000000000001
     if(ans(decimal) < N):
          k -= 1
     else:
          reset 30th position
          ans(binary) = 00000000000000000000000000000001
 Do the same from 29th to 1st position

Answer 2

您必须执行按位运算来快速计算答案。让我给你一些提示。

数字1在二进制和十进制表示法中是相同的：1₂=1₁₀

要使数字10₂=2₁₀，请将1向左移动一个位置。在Java和许多其他语言中，我们可以这样写：

(1 << 1) == 2

要使二进制数100₂=4₁₀，请将1向左移动两个位置：

(1 << 2) == 4

要使二进制数1000₂=8₁₀向左移动1三个位置：

(1 << 3) == 8

你明白了。

要查看某个位置的位是1还是0，请使用

5 & (1 << 2) != 0
5 & (1 << 1) == 0
5 & (1 << 0) != 0

要将位设置为0，请使用按位异或运算符^。例如，我们可以将710=1112的第二有效位设置为0，从而获得510=1012：

7 ^ (1 << 1) == 5

Answer 3

根据更新的问题N可以在2到10^9之间。从N-1开始循环2次，然后循环10^9/2次。不好的。

从M=N-1开始是好的。使用bitCount（M）是很好的开始。如果初始位计数为

但如果不是，请不要循环执行步骤-2。

看到你脑海中的数字是二进制的，例如110101011。位计数为6。假设K是4，这意味着你必须删除2位。最右边的位必须保持在，并且你想要最大的数，所以清除两个倒数第二个1位。结果：110100001。

现在，你想想怎么写。并在不转换为文本的情况下进行。

注：带N