Bug (As I expect) in Binary Shuffle (JUNE18B)

Consider a case where B=0 and A!=0.
The answer as expected is -1.

Let’s consider a test case:


1 0

But the answer should be 64.

Because, we can represent -1 in binary form as well.

-1 = 1111 1111 1111… 64 times in binary representation

(It is not mentioned in the problem that we cannot use binary representation for negative numbers).

So, in 63 steps we can add 63 1’s to A to make it -1

and then add +1 to the result in the 64th step to make it 0.

Tell me if I’m wrong.

We can also represent -1 = 1111 1111 1111… 128 or 256 or 99 or x times. Take x whatever you want. Depending on what we want to take. Question does not say that this binary representation should be same as stored in computers.

What I feel/think is that -1 = -(1*2^0 + 0*2^1+…) etc. just as we represt -123 = -(1*10^2+2*10^2+3*10^0) etc. And behaviour for this is not defined with respected to this question.

1111 1111 1111… 64 times = 2^64-1 and 1111 1111 1111… 64 times !=-1 if you take this case in general instead of signed 64 bit integer.

If we assume signed 32 bit integer then -1 = 1111 1111 1111… 32 times

If we assume signed 64 bit integer. And if constrains were 0<=A,B<=10^1000 . Then ??
This can also be solved with Time Complexity (??) something on lines of O(logA+logB) per test case. But it will require no of test cases to be reduced per test case.

I agree it was not mentioned in question clearly that

##“you cannot use binary representation for negative numbers”
Okay but what about this line mentioned in question…
#“write A as a binary number with an arbitrary number of leading zeroes”
Now if you think representing a number in binary and add arbitrary number of leading zeroes to it then your answer will be a variable as it is not mentioned that how many zeroes to add as lead
what I meant is if considered 0001 then your answer is x… if u write 0000001 your answer will be y

So this is an ambiguity… So you could had asked for it in comment section of problem or you may deduce that probably question was not meant for negative numbers due to “leading zeros” part mentioned in question…

PS : I agree 1111_2 + 0001_2 = 0000_2 in any binary representation system whether it is about computers or not…

Binary representation of negative numbers in C/C++ is also implementation-defined behavior - 64 1’s in a 64bit signed integer doesn’t have to be -1. It usually is, but it doesn’t have to.

So as long as there aren’t an any specifications about the representation of negative integers in the description of a problem involving bit manipulation it is safe to say negative numbers are not allowed.

well. in One’s complement 1111 + 0001 = 0001 = 1 (assuming a 4 bit integer)

well if nothing is mentioned then its not bad considering the simple method of representing it…
1111 + 0001 == 0000 for any representation…
It’s just the rule in 1’s complement system to add one more “0001” to it if you get an end carry
so basically
1111 + 0001 == 0000 and 1 as carry…
Now as per rule you did
0000 + 0001 = 0001 (which was not mentioned in question)

and how u got “1” as “0001” then cuz in Excess-8 representation it is “-7”

I mean there can be many systems to represent positive numbers also… so as u went with simple one for positive numbers… I am going for simple representation for negatives…
PS: it’s not even mentioned about which system to use for positive numbers…
So should I consider that that positives are also not allowed in this question ?? :smiley:

I’m not following. What exactly are you saying?

Are you agreeing with me that “1111 + 0001 = 0000” isn’t true in all binary representations or are you disagreeing with me?

I am disagreeing…

You correctly wrote that the carry bit is always added to the result. So 1111(negative zero) + 0001 (1) = 0001 (1).

Negative Zero plus One equals positive Zero would make no sense.

And the C/C++ standard requires for all bits of unsigned n-bit integers to stand for exactly one power of 2 from 2^0 to 2^(n-1)(so each is represented).

It doesn’t matter how the implementation handles positive integers for this problem(so in what order the bits are written). The standard guarantees the same number of 1’s and this problem is solvable without knowing the binary representation of positive integers.

@l_returns Please elaborate how did you got 1111 + 0001 == 0000 ??
Because Afaik (2^3+2^2+2^1+2^0) + (2^0) = (2^4) i.e. (10000).

1111_2 + 1_2 = 0_2 is really only sensible modulo 16, as in our regular number system the general result is just 1111_2 + 1_2 = 10000_2. The kind of behavior you’re talking about is not at all sensible when dealing with numbers with a variable number of digits.


Bro, I took 64 bit just as an example since the constraints are till 10^18.
Taking 128 or 256 bits will increase the answer :stuck_out_tongue:

I didn’t intend to fight on this. All I wanted to say is that such things should be mentioned in the problem. What if such a problem appeared in a short contest and there you cannot assume anything or would prefer waste your time asking in the comments section and others who didn’t figure out this thing got an AC thus making you lag behind in the ranklist. Right?

I admit I took a wrong title for this question.

1 Like

@algmyr Yes this is what I meant when is said x times. signed 64 bit integer. Please convert this comment into answer. I was waiting for an explaination so that I can counter attack it.