What does int c = (a+b) >>1 mean in C++?
+17
A:
It returns the average of a and b, rounded down. So, if a is 5 and b is 8, then the result is 6.
ETA: This method is busted if a and b add up to a negative number, like if both are negative, or if integer overflow occurs.
Chris Jester-Young
2010-09-23 16:27:37
The `>> 1` is a particularly hack-y way of dividing by 2, because it bit-shifts to the right by 1.
Quartz
2010-09-23 16:28:54
@Quartz: Some people do it as a micro-optimisation because they think the compiler can't handle `/2` properly. I, of course, disagree.
Chris Jester-Young
2010-09-23 16:30:02
Not correct in general case. Since `a + b` can be negative, the behavior of `>>` is implementation-defined.
AndreyT
2010-09-23 16:31:32
@Chris Yeah, but when you write >> 1, it looks like you are smarter:)
Petar Minchev
2010-09-23 16:32:06
@AndreyT: Added a comment addressing your concern. :-)
Chris Jester-Young
2010-09-23 16:32:45
I always disagree with the optimization with some tricky code. 20% of your code will use almost 80% performance of your systems. It must be the place to be optimized, not these things :)
coolkid
2010-09-23 16:39:54
In environments where using the >> operator on signed numbers implements sign extension, saying "exp >> 1" is a way of dividing by two with round-toward-negative-infinity. It's too bad the C standard doesn't require implementations to handle it that way, since it would otherwise often be more useful than "/2".
supercat
2010-09-23 17:04:55
@Petar: I'd have other thoughts...
GMan
2010-09-23 21:42:43
+5
A:
That depends on the type of c, a and b. If it's int then the above statement is the same as:
c = (a+b)/2;
>> means shift right one bit.
ybungalobill
2010-09-23 16:28:11
If `a` or `b` is floating-point, then `>>` doesn't work and the program won't compile anyway. So, we'll safely assume they're both integral.
Chris Jester-Young
2010-09-23 16:34:36
Not the same if it's negative. If it's `unsigned int`, then that works.
Michael Mior
2010-09-23 17:02:30
@ybungalobill: do you have a source for that? I'm pretty sure that arithmetic shifts are defined as shifts that use the high bit to fill in the missing bits. As such shifting a negative number would always round down (i.e. -15>>1 == -8).
Niki Yoshiuchi
2010-09-23 17:17:11
@Niki Yoshiuchi: Sorry I've already deleted my answer for another reason. Per your question: For right bit-shift it's implementation-define which bit is shifted for **negative** numbers (signed non-negative is OK), see [expr.shift]. For division it's actually defined that it's rounded towards zero thus I deleted my answer.
ybungalobill
2010-09-23 17:21:08
You just broke the merge sort, buddy http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Hamish Grubijan
2010-09-28 19:10:43
+1
A:
It means that you add a and b, then shift the result one bit to the right.
It's the same as:
int c = (a + b) / 2;
Guffa
2010-09-23 16:29:10
Fail :)http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Hamish Grubijan
2010-09-28 19:11:26
+2
A:
It means to add A to B, then bit-shift the result by one bit to the right. Bit-shifting a positive integer generally has the effect of multiplying or dividing by 2^n where n is the number of bits being shifted. So, this is roughly equivalent to (a+b)/2 in integer math (which has no remainders or fractional parts).
KeithS
2010-09-23 16:30:07
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Hamish Grubijan
2010-09-28 19:11:51
+9
A:
Note, that there can't be any meaningful explanation of what your code means until you explain what a and b are.
Even if a and b are of built-in type, beware of the incorrect answers unconditionally claiming that built-in right shift is equivalent to division by 2. The equivalence only holds for non-negative values. The behavior of the >> operator for negative values is implementation-defined.
In other words, without extra information, the only thing that can be said is that the code calculates the "sum" a + b and "shifts" it right by 1 bit. I used quotes in the last sentence because in case of overloaded operators + and >> there's no way to predict what they are doing.
AndreyT
2010-09-23 16:33:22
Agree, though, my answer was trying to address the intent of the code, rather than what it actually does.
Chris Jester-Young
2010-09-23 16:39:38
In more detail, a twos-complement negative number starts with 1 (negative numbers are 2^n-x, where n is the number of bits used to store a number and x is the absolute value of the number). A strict bit-shift of that number to the left will replace this 1 with a zero; in decimal math the transformation would follow abs(x)/2+2^(n-1)
KeithS
2010-09-23 16:44:10
@KeithS: Right, and that's what AndreyT's point is: it's implementation-defined. On x86, there are two instructions, `SHR` and `SAR`. `SHR` does what you say: shifts in 0. `SAR` shifts in the top bit. So, since compilers are free to choose which instruction to use, you can get varied results.
Chris Jester-Young
2010-09-23 23:35:47
What about the overflow? http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Hamish Grubijan
2010-09-28 19:12:27
+1
A:
As mentioned above, it's an average function utilizing the bit-shift operator in c++ (with some potential pitfalls in it) - by the existence of this question, the readability of this code is quite bad. Do your fellow programmer a favor and think about readability when you write code
bigtang
2010-09-23 16:38:06