百度笔试真题-最小对冲值(C++/Py/Java /Js/Go)

最小对冲值

百度技术岗 笔试真题 8月6号 第二题

题目内容

调度模块要把一个非负整型额度mmm拆成两份：任选整型yyy（0≤y≤m0 \le y \le m0≤y≤m），另一份为m−ym-ym−y。定义这次拆分的「对冲值」为
G(y)=y⊕(m−y)G(y)=y \oplus (m-y)G(y)=y⊕(m−y)
其中⊕\oplus⊕为按位异或（对应二进制位相同得000、不同得111）。例如6 (1102)6\ (110_2)6(1102​)与1 (0012)1\ (001_2)1(0012​)满足6 xor 1=7 (1112)6\ \text{xor}\ 1 = 7\ (111_2)6xor1=7(1112​)。现给定若干个额度，请对每个mmm求出可取到的最小对冲值。

输入描述

第一行一个整型nnn(1≤n≤105)(1 \le n \le 10^5)(1≤n≤105)，表示随后有nnn行额度。
接下来nnn行，每行一个整型mmm(1≤m≤1018)(1 \le m \le 10^{18})(1≤m≤1018)。
请对每个mmm逐一计算其最小对冲值。

输出描述

共输出nnn行；对于每一个mmm，写出一个非负整型，即
min⁡(0⊕m, 1⊕(m−1), 2⊕(m−2), …, m⊕0)\min\bigl(0\oplus m,\ 1\oplus(m-1),\ 2\oplus(m-2),\ \ldots,\ m\oplus 0\bigr)min(0⊕m,1⊕(m−1),2⊕(m−2),…,m⊕0)

样例1

输入

3 4 5 11

输出

0 1 3

说明
三个额度依次为4,5,114,5,114,5,11：取y=2y=2y=2时2⊕2=02\oplus 2=02⊕2=0；取y=2y=2y=2时2⊕3=12\oplus 3=12⊕3=1；取y=4y=4y=4时4⊕7=34\oplus 7=34⊕7=3。

样例2

输入

2 2 7

输出

0 7

说明
额度222：取y=1y=1y=1得1⊕1=01\oplus 1=01⊕1=0。额度777：枚举可知最小对冲值为777。

题解

思路

数学原理

1. 二进制加法公式a + b = (a ^ b) + 2 * (a & b)=>a ^ b = a + b - 2 * (a & b)
2. 对应到此题中y ^ (m - y) = m - 2 * (y & (m - y))最小值就是让y & (m - y)尽可能大。就是让两个数接近。所以选择两个数分别为m /2和(m + 1) /2

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intm;cin>>m;cout<<((m/2)^((m+1)/2))<<endl;}return0;}

java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intT=sc.nextInt();while(T-->0){intm=sc.nextInt();System.out.println((m/2)^((m+1)/2));}sc.close();}}

python

importsys# 读取输入data=sys.stdin.read().split()T=int(data[0])idx=1whileT>0:m=int(data[idx])idx+=1print((m//2)^((m+1)//2))T-=1

javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",function(line){input.push(...line.trim().split(/\s+/));});rl.on("close",function(){letidx=0;letT=Number(input[idx++]);console.log(T);while(T>0){T--;letm=Number(input[idx++]);console.log((Math.floor(m/2))^(Math.floor((m+1)/2)));}});

Go

packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,&T)out:=bufio.NewWriter(os.Stdout)deferout.Flush()forT>0{varmintfmt.Fscan(in,&m)fmt.Fprintln(out,(m/2)^((m+1)/2))T--}}