gpt4 book ai didi

java - 使用按位移位运算符进行相乘,得到 TLE

转载 作者:太空宇宙 更新时间:2023-11-04 11:08:07 29 4
gpt4 key购买 nike

Question

Given N and M, write an equation using left shift operators whose result will be equal to the product N * M.

Input : First line has 0 < T ≤ 50000 denoting number of test cases.
Next T lines have two integers 0 < N, M ≤ 10¹⁶.

Output : For each test case print an equation for N * M resembling

(N << p1) + (N << p2)+ ...+(N << pk) where p1 ≥ p2 ≥ ... ≥ pk and k is minimum.

SAMPLE INPUT    SAMPLE OUTPUT

2
2 1 (2<<0)
2 3 (2<<1) + (2<<0)

Time Limit: 1.0 sec

我的解决方案第一种方法

int dig = (int)(Math.floor(Math.log10(m)/Math.log10(2))+1);
boolean flag = false;
for(long i = dig; i>=0; --i) {
if(((m>>(i-1l)) & 1l) == 1l) {
if(flag)
System.out.print(" + ("+n+ "<<"+(i-1)+")");
else {
System.out.print("("+n+"<<"+(i-1)+")");
flag = true;
}
}
}

第二种方法

boolean[] arr = new boolean[dig];
int i = dig-1;
while(m > 0) {
if((m&1) == 1 ) {
arr[i] = true;
}
i--;
m = m>>1l;
}
int j = dig-1;
for( i = 0; i < dig; ++i) {

if(arr[i]) {
if(flag)
System.out.print(" + ("+n+"<<"+j+")");
else {
System.out.print("("+n+"<<"+j+")");
flag = true;
}
}

j--;
}

在这两种情况下,我在 8 题中得到了 5 题,其余 3 题都是 TLE,为什么?

最佳答案

实际上,我并没有看到您的两种方法中存在任何阻止最多 57 位数字的数万个乘积在一秒钟内表示为 String 的情况:
TLE 可能是由于 System.out.print() 花费了过多的时间。
也就是说,使用像这样的实用程序

   /** builds <code>n * m</code> in the form
* <code>(n&lt;&lt;p1) + (n&lt;&lt;p2) + ... + (n&lt;&lt;pk)</code>
* using left shift.
* @param n (0 < multiplicand <= 10**16)
* @param m 0 < multiplier <= 10**16
* @return a verbose <code>String</code> for <code>n * m</code>
*/
static String verboseBinaryProduct(Object n, long m) {
int shift = Long.SIZE - Long.numberOfLeadingZeros(m) - 1;
final long highest = 1 << shift;
final StringBuilder binary = new StringBuilder(42);
final String chatter = ") + (" + n + "<<";
final long rest = highest - 1;
while (true) {
if (0 != (highest & m))
binary.append(chatter).append(shift);
if (0 == (rest & m)) {
binary.append(')');
return binary.substring(4);
}
m <<= 1;
shift -= 1;
}
}

System.out.println(verboseBinaryProduct(n, m));

关于java - 使用按位移位运算符进行相乘,得到 TLE,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46270676/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com