I have a problem where I have to do left shift and right shift. Long N; int shiftby; output = N >> shiftby; Above N is shifted right. Example if N=11101101 [binary value] will become: 1110110 when shiftby=1; will become: 0111011 when shiftby=2; will become: 0011101 when shiftby=3; will become: 0001110 when shiftby=4; will become: 0000111 when shiftby=5; will become: 0000011 when shiftby=6; will become: 0000001 when shiftby=7; When I want to shift left I can use output = N << shiftby; //[Not change in sign "<<" instead of ">>"] Above N is shifted left. Example if N=11101101 [binary value] will become: 111011010 when shiftby=1; will become: 1110110100 when shiftby=2; will become: 11101101000 when shiftby=3; will become: 111011010000 when shiftby=4; will become: 1110110100000 when shiftby=5; will become: 11101101000000 when shiftby=6; will become: 111011010000000 when shiftby=7; I have to use use left shift and right shift to shift Number right/ left depending on value of shiftby if (shift>0) output = N >> shiftby; else output = N << (-shiftby);// working but inefficient. I am using above shift operator many times. I want to get rid of the if then else condition. As If condition takes a lot of time. I want something like output = N >> shiftby; where N is shifted left / right automatically if shiftby is -ve then shift left otherwise shift right. I tried using below function divider=2^shiftby; //<<=== Is it not 2*2* ... shiftby times???? math.pow() can also be used output = N * divider;// automatically shifts left right depending on value of divider But this seems not to work. math.pow() is again time consuming function. Can I use it? how much faster is math.pow() function compared to if conditions? Is there any way to avoid the if condition and do right shift and left shift using operators depending on shiftby is +ve or -ve? Bye Sanny Java Experts needed http://www.GetClub.com/Experts.php [Lots of coding jobs to choose]
Sanny wrote: > I have a problem where I have to do left shift and right shift. > [...] > > I have to use use left shift and right shift to shift Number right/ > left depending on value of shiftby > > if (shift>0) output = N >> shiftby; else output = N << (-shiftby);// > working but inefficient. In what way is it inefficient? Have you performed measurements or do you simply think that it's slow and want to optimize it prematurely? Regards, Lothar -- Lothar Kimmeringer E-Mail: spamfang@kimmeringer.de PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81) Always remember: The answer is forty-two, there can only be wrong questions!
> Is there any way to avoid the if condition and do right shift and left > shift using operators depending on shiftby is +ve or -ve? I used below technique but it gives error. divider=Math.pow(2,shiftby); then output = (long) N / divider; This works for most cases but failed when output is greater than 9223372036854775807 N="9223372036854775807"; and shift by (-3); long output=(long)(9223372036854775807 / 0.125); The answer is "-1"; binary Value: 111111111111111111111111111111111111111111111111111111111111111 While correct answer is : 1000000000000000000000000000000000000000000000000000000000000000 It is because "long" is 64 bit signed variable. Can I get unsigned Long? Or bigger than long variable? So that 64 bit shifts can be done easily? Bye Sanny Java Experts needed http://www.GetClub.com/Experts.php [Lots of coding jobs to choose]
On 4/26/2011 12:55 AM, Lothar Kimmeringer wrote: > Sanny wrote: > >> I have a problem where I have to do left shift and right shift. >> > [...] >> >> I have to use use left shift and right shift to shift Number right/ >> left depending on value of shiftby >> >> if (shift>0) output = N>> shiftby; else output = N<< (-shiftby);// >> working but inefficient. > > In what way is it inefficient? Have you performed measurements > or do you simply think that it's slow and want to optimize > it prematurely? It is very important that the measurement be done in context, using the pattern of left and right shifts that occur in the real program. The very worst possible case is the one that many people might use in a test program, a random, equal probability, mix of left and right shifts. That makes the hardware branch prediction no better than random. Patricia
On 4/26/2011 5:04 AM, Sanny wrote: >> Is there any way to avoid the if condition and do right shift and left >> shift using operators depending on shiftby is +ve or -ve? > > I used below technique but it gives error. > > divider=Math.pow(2,shiftby); > then > output = (long) N / divider; Let me get this straight: You're worried about the inefficiency of an `if' that chooses between a left or a right shift, so you plan to eliminate the `if' by evaluating an exponential function? ARE YOU OUT OF YOUR MIND? -- Eric Sosman esosman@ieee-dot-org.invalid
On 04/26/2011 03:38 AM, Sanny wrote: > divider=2^shiftby; //<<=== Is it not 2*2* ... shiftby times???? the `^' here is the XOR operator, not an exponentiation operator. > math.pow() is again time consuming function. Can I use it? how much > faster is math.pow() function compared to if conditions? Math.pow is S - L - O - W compared to an if and a shift. Barrel shifting can be done in the same amount of time as integer addition (circuit depth is both O(lg N) in both cases), while Math.pow is a function that works with floating point (typically slower than integer math anyways), has lower precision (53 bits for double, 63 bits for long), and requires a lot more computation. This is a listing I have for the implementation of Math.pow, courtesy of OpenJDK: double __ieee754_pow(double x, double y) { double z,ax,z_h,z_l,p_h,p_l; double y1,t1,t2,r,s,t,u,v,w; int i0,i1,i,j,k,yisint,n; int hx,hy,ix,iy; unsigned lx,ly; i0 = ((*(int*)&one)>>29)^1; i1=1-i0; hx = __HI(x); lx = __LO(x); hy = __HI(y); ly = __LO(y); ix = hx&0x7fffffff; iy = hy&0x7fffffff; /* y==zero: x**0 = 1 */ if((iy|ly)==0) return one; /* +-NaN return x+y */ if(ix > 0x7ff00000 || ((ix==0x7ff00000)&&(lx!=0)) || iy > 0x7ff00000 || ((iy==0x7ff00000)&&(ly!=0))) return x+y; /* determine if y is an odd int when x < 0 * yisint = 0 ... y is not an integer * yisint = 1 ... y is an odd int * yisint = 2 ... y is an even int */ yisint = 0; if(hx<0) { if(iy>=0x43400000) yisint = 2; /* even integer y */ else if(iy>=0x3ff00000) { k = (iy>>20)-0x3ff; /* exponent */ if(k>20) { j = ly>>(52-k); if((j<<(52-k))==ly) yisint = 2-(j&1); } else if(ly==0) { j = iy>>(20-k); if((j<<(20-k))==iy) yisint = 2-(j&1); } } } /* special value of y */ if(ly==0) { if (iy==0x7ff00000) { /* y is +-inf */ if(((ix-0x3ff00000)|lx)==0) return y - y; /* inf**+-1 is NaN */ else if (ix >= 0x3ff00000)/* (|x|>1)**+-inf = inf,0 */ return (hy>=0)? y: zero; else /* (|x|<1)**-,+inf = inf,0 */ return (hy<0)?-y: zero; } if(iy==0x3ff00000) { /* y is +-1 */ if(hy<0) return one/x; else return x; } if(hy==0x40000000) return x*x; /* y is 2 */ if(hy==0x3fe00000) { /* y is 0.5 */ if(hx>=0) /* x >= +0 */ return sqrt(x); } } ax = fabs(x); /* special value of x */ if(lx==0) { if(ix==0x7ff00000||ix==0||ix==0x3ff00000){ z = ax; /*x is +-0,+-inf,+-1*/ if(hy<0) z = one/z; /* z = (1/|x|) */ if(hx<0) { if(((ix-0x3ff00000)|yisint)==0) { z = (z-z)/(z-z); /* (-1)**non-int is NaN */ } else if(yisint==1) z = -1.0*z; /* (x<0)**odd = -(|x|**odd) */ } return z; } } n = (hx>>31)+1; /* (x<0)**(non-int) is NaN */ if((n|yisint)==0) return (x-x)/(x-x); s = one; /* s (sign of result -ve**odd) = -1 else = 1 */ if((n|(yisint-1))==0) s = -one;/* (-ve)**(odd int) */ /* |y| is huge */ if(iy>0x41e00000) { /* if |y| > 2**31 */ if(iy>0x43f00000){ /* if |y| > 2**64, must o/uflow */ if(ix<=0x3fefffff) return (hy<0)? huge*huge:tiny*tiny; if(ix>=0x3ff00000) return (hy>0)? huge*huge:tiny*tiny; } /* over/underflow if x is not close to one */ if(ix<0x3fefffff) return (hy<0)? s*huge*huge:s*tiny*tiny; if(ix>0x3ff00000) return (hy>0)? s*huge*huge:s*tiny*tiny; /* now |1-x| is tiny <= 2**-20, suffice to compute log(x) by x-x^2/2+x^3/3-x^4/4 */ t = ax-one; /* t has 20 trailing zeros */ w = (t*t)*(0.5-t*(0.3333333333333333333333-t*0.25)); u = ivln2_h*t; /* ivln2_h has 21 sig. bits */ v = t*ivln2_l-w*ivln2; t1 = u+v; __LO(t1) = 0; t2 = v-(t1-u); } else { double ss,s2,s_h,s_l,t_h,t_l; n = 0; /* take care subnormal number */ if(ix<0x00100000) {ax *= two53; n -= 53; ix = __HI(ax); } n += ((ix)>>20)-0x3ff; j = ix&0x000fffff; /* determine interval */ ix = j|0x3ff00000; /* normalize ix */ if(j<=0x3988E) k=0; /* |x|<sqrt(3/2) */ else if(j<0xBB67A) k=1; /* |x|<sqrt(3) */ else {k=0;n+=1;ix -= 0x00100000;} __HI(ax) = ix; /* compute ss = s_h+s_l = (x-1)/(x+1) or (x-1.5)/(x+1.5) */ u = ax-bp[k]; /* bp[0]=1.0, bp[1]=1.5 */ v = one/(ax+bp[k]); ss = u*v; s_h = ss; __LO(s_h) = 0; /* t_h=ax+bp[k] High */ t_h = zero; __HI(t_h)=((ix>>1)|0x20000000)+0x00080000+(k<<18); t_l = ax - (t_h-bp[k]); s_l = v*((u-s_h*t_h)-s_h*t_l); /* compute log(ax) */ s2 = ss*ss; r = s2*s2*(L1+s2*(L2+s2*(L3+s2*(L4+s2*(L5+s2*L6))))); r += s_l*(s_h+ss); s2 = s_h*s_h; t_h = 3.0+s2+r; __LO(t_h) = 0; t_l = r-((t_h-3.0)-s2); /* u+v = ss*(1+...) */ u = s_h*t_h; v = s_l*t_h+t_l*ss; /* 2/(3log2)*(ss+...) */ p_h = u+v; __LO(p_h) = 0; p_l = v-(p_h-u); z_h = cp_h*p_h; /* cp_h+cp_l = 2/(3*log2) */ z_l = cp_l*p_h+p_l*cp+dp_l[k]; /* log2(ax) = (ss+..)*2/(3*log2) = n + dp_h + z_h + z_l */ t = (double)n; t1 = (((z_h+z_l)+dp_h[k])+t); __LO(t1) = 0; t2 = z_l-(((t1-t)-dp_h[k])-z_h); } /* split up y into y1+y2 and compute (y1+y2)*(t1+t2) */ y1 = y; __LO(y1) = 0; p_l = (y-y1)*t1+y*t2; p_h = y1*t1; z = p_l+p_h; j = __HI(z); i = __LO(z); if (j>=0x40900000) { /* z >= 1024 */ if(((j-0x40900000)|i)!=0) /* if z > 1024 */ return s*huge*huge; /* overflow */ else { if(p_l+ovt>z-p_h) return s*huge*huge; /* overflow */ } } else if((j&0x7fffffff)>=0x4090cc00 ) { /* z <= -1075 */ if(((j-0xc090cc00)|i)!=0) /* z < -1075 */ return s*tiny*tiny; /* underflow */ else { if(p_l<=z-p_h) return s*tiny*tiny; /* underflow */ } } /* * compute 2**(p_h+p_l) */ i = j&0x7fffffff; k = (i>>20)-0x3ff; n = 0; if(i>0x3fe00000) { /* if |z| > 0.5, set n = [z+0.5] */ n = j+(0x00100000>>(k+1)); k = ((n&0x7fffffff)>>20)-0x3ff; /* new k for n */ t = zero; __HI(t) = (n&~(0x000fffff>>k)); n = ((n&0x000fffff)|0x00100000)>>(20-k); if(j<0) n = -n; p_h -= t; } t = p_l+p_h; __LO(t) = 0; u = t*lg2_h; v = (p_l-(t-p_h))*lg2+t*lg2_l; z = u+v; w = v-(z-u); t = z*z; t1 = z - t*(P1+t*(P2+t*(P3+t*(P4+t*P5)))); r = (z*t1)/(t1-two)-(w+z*w); z = one-(r-z); j = __HI(z); j += (n<<20); if((j>>20)<=0) z = scalbn(z,n); /* subnormal output */ else __HI(z) += (n<<20); return s*z; } Well over a hundred lines of code, and consisting minimally of 1 if statement and maximally of around 2-3 dozen if statements. All to avoid a single if statement? I think not. With modern branch prediction, you'd probably lose out an amortized cost of a dozen clock cycles or so with that branch prediction, and there are some systems where the branch essentially becomes free (good candidate for predicates). If you're really that worried about a single if statement, then the sanity checks on your input parameters must be killing you. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
On 04/26/2011 07:34 AM, Eric Sosman wrote: > On 4/26/2011 5:04 AM, Sanny wrote: >>> Is there any way to avoid the if condition and do right shift and left >>> shift using operators depending on shiftby is +ve or -ve? >> >> I used below technique but it gives error. >> >> divider=Math.pow(2,shiftby); >> then >> output = (long) N / divider; > > Let me get this straight: You're worried about the inefficiency > of an `if' that chooses between a left or a right shift, so you plan > to eliminate the `if' by evaluating an exponential function? > > ARE YOU OUT OF YOUR MIND? Especially given that shift is blazingly efficient on just about any computer that supports Java. You're optimizing something that's used *as* an optimization, Sanny-Boy. Answer the questions people ask you, Sanny-Boy. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Lothar Kimmeringer wrote: > Sanny wrote: > >> I have a problem where I have to do left shift and right shift. >> > [...] >> >> I have to use use left shift and right shift to shift Number right/ >> left depending on value of shiftby >> >> if (shift>0) output = N>> shiftby; else output = N<< (-shiftby);// >> working but inefficient. > In what way is it inefficient? Have you performed measurements > or do you simply think that it's slow and want to optimize > it prematurely? Sanny-Boy, I see that you posted after Lothar asked you this very, very important question but that you did not answer this question. This is a conversation, not a bunch of lackeys leaping to your bid. Please answer the questions. You claim inefficiency in something you have no clue whatsoever to be inefficient. Here's another question, assuming you answer Lothar's question at all, if you did perform measurements, what were the results? -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On 26/04/2011 6:49 AM, Lew wrote: > Lothar Kimmeringer wrote: >> Sanny wrote: >> >>> I have a problem where I have to do left shift and right shift. >>> >> [...] >>> >>> I have to use use left shift and right shift to shift Number right/ >>> left depending on value of shiftby >>> >>> if (shift>0) output = N>> shiftby; else output = N<< (-shiftby);// >>> working but inefficient. > >> In what way is it inefficient? Have you performed measurements >> or do you simply think that it's slow and want to optimize >> it prematurely? > > Sanny-Boy, I see that you posted after Lothar asked you this very, very > important question but that you did not answer this question. > > This is a conversation, not a bunch of lackeys leaping to your bid. > Please answer the questions. > > You claim inefficiency in something you have no clue whatsoever to be > inefficient. > > Here's another question, assuming you answer Lothar's question at all, > if you did perform measurements, what were the results? And people claimed I was being arrogant to insist people learn to program before they learn Java...
On 26/04/2011 2:04 AM, Sanny wrote: >> Is there any way to avoid the if condition and do right shift and left >> shift using operators depending on shiftby is +ve or -ve? > > I used below technique but it gives error. > > divider=Math.pow(2,shiftby); > then > output = (long) N / divider; My advice: if (shift>0) output = N >> shiftby; else output = N << (-shiftby); The above is pretty efficient, and once the hotspot compiler gets a hold of it, it will be even faster. There is no assembly operator that shifts based on +/- bits; there are only shift-left and shift-right operators. If there was a Java operator/function to do what you want, it would still be implemented (in machine language) as: if (shift>0) output = N >> shiftby; else output = N << (-shiftby); But I am curious why you consider the "if" test is expensive? The usual rules for optimization: 1. Profile your code 2. Determine where your code is spending most of its time 3. Re-visit your algorithm and decide if you are using the right algorithm. 3a. If so, optimize the methods that are consuming most of the time. 3b. Implement a better algorithm and repeat these processes.
On 04/26/2011 10:09 AM, Travers Naran wrote: > Lew wrote: >> Here's another question, assuming you answer Lothar's question at all, >> if you did perform measurements, what were the results? > > And people claimed I was being arrogant to insist people learn to program > before they learn Java... That's not arrogant, that's intelligent. I agree mostly, although I believe it possible to learn both concurrently. People most certainly should learn to program before they get paid to. And I'm not arrogant, I'm supercilious. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Travers Naran wrote: > Sanny wrote: >>> Is there any way to avoid the if condition and do right shift and left >>> shift using operators depending on shiftby is +ve or -ve? >> >> I used below technique but it gives error. >> >> divider=Math.pow(2,shiftby); Please follow Java naming conventions. >> then >> output = (long) N / divider; > My advice: > if (shift>0) output = N >> shiftby; else output = N << (-shiftby); > > The above is pretty efficient, and once the hotspot compiler gets a hold of > it, it will be even faster. > > There is no assembly operator that shifts based on +/- bits; there are only > shift-left and shift-right operators. If there was a Java operator/function to > do what you want, it would still be implemented (in machine language) as: Doesn't matter, the Java operator *is* defined for negative values. So the solution to Sanny's problem is: output = n >> shiftBy; -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Lew wrote: > Doesn't matter, the Java operator *is* defined for negative values. > > So the solution to Sanny's problem is: > > output = n >> shiftBy; OK, that is a trick answer because it's wrong. True, the shift operator is defined for negative shift values, but those get masked to positive shift values regardless and don't give the OP's desired result. Consider shifting an int by either 12 or -12 12 = 0b00001100 -12 = 0b11110100 The bottom five bits of the latter evaluate to 20. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On Tue, 26 Apr 2011 07:09:53 -0700, Travers Naran wrote: > And people claimed I was being arrogant to insist people learn to > program before they learn Java... They were right. Java is a good choice for a programming neophyte because it imposes a sensible structure on the code being written. -- martin@ | Martin Gregorie gregorie. | Essex, UK org |
> This is a conversation, not a bunch of lackeys leaping to your bid. =A0Pl= ease > answer the questions. Sorry, for that. I wanted to be short. not going into long discussions. > You claim inefficiency in something you have no clue whatsoever to be ine= fficient. > > Here's another question, assuming you answer Lothar's question at all, if= you > did perform measurements, what were the results? I have computed and found "if statments" take 20-50 times longer than basic arithmetic operations. So I wanted to replace if condition by some arithmetics/ Maths. Bye Sanny
> >> Is there any way to avoid the if condition and do right shift and left > >> shift using operators depending on shiftby is +ve or -ve? > > > I used below technique but it gives error. > > > divider=3DMath.pow(2,shiftby); > > then > > output =3D (long) N / divider; > > =A0 =A0 =A0Let me get this straight: You're worried about the inefficienc= y > of an `if' that chooses between a left or a right shift, so you plan > to eliminate the `if' by evaluating an exponential function? > > =A0 =A0 =A0ARE YOU OUT OF YOUR MIND? I didnt knew how much inefficient it is. I heard Math. (...) functions are very fast and they use Native support like assembly language so they are quite faster. Is there a "Integer" in java which is longer than 64 bits? byte: 8 bits short: ??? int: 16/32 bits long: 64 bit any 128 bit integer??? I want something that can handle more bits than long. and I am able to do bit operations on them. I have heard of BigInteger I dont know how many bits it supports. Can I use byte[] to represent a longer number and do multiplications/ divisions on them? Bye Sanny
> > Doesn't matter, the Java operator *is* defined for negative values. > > > So the solution to Sanny's problem is: > > > output =3D n >> shiftBy; > > OK, that is a trick answer because it's wrong. =A0True, the shift operato= r is > defined for negative shift values, but those get masked to positive shift > values regardless and don't give the OP's desired result. I did not get any error when using it but the answer was "0" when I used negative shifts. Maximum value a integer can hold is 64 bit in long variable. I want a even larger number. Can I create a larger number which allows right- shifts and left shifts? by multiplication/ division? Bye Sanny
On 4/26/2011 9:32 AM, Sanny wrote: .... > I have computed and found "if statments" take 20-50 times longer than > basic arithmetic operations. So I wanted to replace if condition by > some arithmetics/ Maths. .... You are seriously underestimating the range of variation of if-statement time. It can be just as fast as an arithmetic statement. It must be measured in context - you could be wasting your time if the actual mix of left and right shifts has a pattern the branch predictor can pick up. Patricia
On 4/26/2011 9:39 AM, Sanny wrote: .... > I have heard of BigInteger I dont know how many bits it supports. .... BigInteger uses int to index the bits, so it cannot contain more than Integer.MAX_VALUE bits. > Can I use byte[] to represent a longer number and do multiplications/ > divisions on them? You could, with a lot of work, but the result would be a less efficient version of BigInteger. BigInteger uses int[] internally to store the data, reducing the number of separate operations when operating on a large number. Patricia
Sanny, please attribute your citations. Sanny wrote: >>>> Is there any way to avoid the if condition and do right shift and left >>>> shift using operators depending on shiftby is +ve or -ve? >> >>> I used below technique but it gives error. >> >>> divider=Math.pow(2,shiftby); >>> then >>> output = (long) N / divider; Eric Sosman wrote: >> Let me get this straight: You're worried about the inefficiency >> of an `if' that chooses between a left or a right shift, so you plan >> to eliminate the `if' by evaluating an exponential function? >> >> ARE YOU OUT OF YOUR MIND? Sanny wrote: > I didnt knew how much inefficient it is. I heard Math. (...) functions > are very fast and they use Native support like assembly language so > they are quite faster. Whence did you hear that? Please let us know the source(s). Think through on the basis of fundamental computer science. Math.xxx() methods on floating point ('float' and 'double') are always going to be slower than integer operations, particularly single-instruction operations like shift. However, the difference isn't always going to matter. So when some anonymous, untrusted source tells you that a Math.xxx() method is "very fast", the context OBVIOUSLY is relative to other implementations of the same functionality, not "'Math.pow()' is faster than '>>>'". If you saw *that* claim, throw away the source immediately. Programming is an art that requires the practitioner to *think*. Cargo-cult reactions based on no evidence or reason or even thought, such as "Math.pow() is 'very fast', so I'll use it instead of shift operators without measuring first what impact if any the shift operators have on actual performance." > Is there a "Integer" in java [psic] which is longer than 64 bits? RTFM. [1] > byte: 8 bits > short: ??? > int: 16/32 bits Where do you get this? Type sizes in Java are fixed to particular values, not "16/32". > long: 64 bit > > any 128 bit integer??? How many question marks does it take to indicate an interrogative? > I want something that can handle more bits than long. and I am able to > do bit operations on them. > > I have heard of BigInteger I dont know how many bits it supports. RTFM. [2] > Can I use byte[] to represent a longer number and do multiplications/ > divisions on them? Yes. But why would you? As for RTFMing, you will make zero progress as a programmer, in fact, you are not even a programmer unless you habitually and competently read and comprehend the documentation. One who does not habitually and competently read and comprehend the documentation will learn less than nothing from questions asked and answers received of Usenet. Assimilation of that advice will accelerate your skills a thousandfold. [1] <http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.2.1> [2] <http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html> -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Lew wrote: >> ... java [psic] ... self-[sic] -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Sanny, please attribute your citations. Sanny wrote: >>> Doesn't matter, the Java operator *is* defined for negative values. See? You didn't write that. Sanny wrote: > Lew wrote: >>> Doesn't matter, the Java operator *is* defined for negative values. >>> So the solution to Sanny's problem is: >> >>> output = n>> shiftBy; >> >> OK, that is a trick answer because it's wrong. True, the shift operator is >> defined for negative shift values, but those get masked to positive shift >> values regardless and don't give the OP's desired result. Sanny wrote: > I did not get any error when using it but the answer was "0" when I > used negative shifts. What was the shift value you used? What were the lower five bits of the right operand (if the left operand was 'int') or six bits (if the left operand was 'long')? > Maximum value a integer can hold is 64 bit in long variable. I want a > even larger number. Can I create a larger number which allows right- > shifts and left shifts? by multiplication/ division? RTFM. <http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html#shiftLeft(int)> <http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html#shiftRight(int)> RTFM. RTFM. RTFM. RTFM. RTFM. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On 26/04/2011 20:55, Lew allegedly wrote: > "'Math.pow()' is faster than '>>>'". If you saw *that* claim, throw > away the source immediately. And then beat it to a pulp and put its head on a pike, for good measure. -- DF. An escaped convict once said to me: "Alcatraz is the place to be"
On 26.04.2011 09:38, Sanny wrote: > output = N<< shiftby; //[Not change in sign "<<" instead of">>"] I am not sure what you mean by that comment. Just for completeness reasons I want to make sure you are aware of operator ">>>": http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#5121 Cheers robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/
On 4/26/2011 11:09 AM, Patricia Shanahan wrote: > On 4/26/2011 9:32 AM, Sanny wrote: > ... >> I have computed and found "if statments" take 20-50 times longer than >> basic arithmetic operations. So I wanted to replace if condition by >> some arithmetics/ Maths. > ... > > You are seriously underestimating the range of variation of if-statement > time. It can be just as fast as an arithmetic statement. It must be > measured in context - you could be wasting your time if the actual mix > of left and right shifts has a pattern the branch predictor can pick up. Incidentally, one of the fastest cases arises during multi-word shifting. Each word in the shift will have the same pattern of taken and not-taken branches. If you do an N-word shift, about (N-1)/N branches will be correctly predicted by just about any reasonable algorithm, and go as fast as a simple arithmetic operation. The Math methods also need to be measured. The native implementations will use whatever fast hardware is available, but some operations may not have hardware support on every system. Patricia
Lew <noone@lewscanon.com> wrote: > Sanny, please attribute your citations. > Sanny wrote: [sic*] >>>>> Is there [...] > Eric Sosman wrote: [sic*] >>> Let me [...] > Sanny wrote: >> I didnt [...] *: Two of three attributions (intendly?) wrongly indented. Lew, please indent attributions with the correct number of ">"s.
On 4/26/2011 12:39 PM, Sanny wrote: >>>> Is there any way to avoid the if condition and do right shift and left >>>> shift using operators depending on shiftby is +ve or -ve? >> >>> I used below technique but it gives error. >> >>> divider=Math.pow(2,shiftby); >>> then >>> output = (long) N / divider; >> >> Let me get this straight: You're worried about the inefficiency >> of an `if' that chooses between a left or a right shift, so you plan >> to eliminate the `if' by evaluating an exponential function? >> >> ARE YOU OUT OF YOUR MIND? > > I didnt knew how much inefficient it is. I heard Math. (...) functions > are very fast and they use Native support like assembly language so > they are quite faster. "Fast" is not an absolute, and neither is "very fast." If you plant an acorn today and have a fifty-foot oak tree in ten years, that's "fast." If you strike a match now and see a flame in ten minutes, that's "slow" even though its half a million times faster than the "fast" oak tree. In other words, interpret "fast" in relation to the amount of work being done. > Is there a "Integer" in java which is longer than 64 bits? > [...] > I have heard of BigInteger I dont know how many bits it supports. Perhaps the Javadoc for BigInteger might be helpful? Oh, no, sorry, that's *way* too obvious, there must be a grue waiting for anyone who tries to read the Javadoc. Never mind. > Can I use byte[] to represent a longer number and do multiplications/ > divisions on them? No. Somebody else could, if he were sufficiently masochistic, but at your present level of Java proficiency[*] it's pretty clear that you cannot. [*] No offense: We all begin from ignorance. Your progress from the starting point is not yet enough to enable you to do this task. -- Eric Sosman esosman@ieee-dot-org.invalid
On 04/26/2011 07:32 PM, Andreas Leitgeb wrote: > Lew<noone@lewscanon.com> wrote: >> Sanny, please attribute your citations. >> Sanny wrote: [sic*] >>>>>> Is there [...] >> Eric Sosman wrote: [sic*] >>>> Let me [...] >> Sanny wrote: >>> I didnt [...] > > *: Two of three attributions (intendly?) wrongly indented. > > Lew, please indent attributions with the correct number of ">"s. Obviously you neglected to see how far back these quotes came. The indentations were correct. Check again. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On 26/04/2011 9:32 AM, Sanny wrote: > I have computed and found "if statments" take 20-50 times longer than > basic arithmetic operations. So I wanted to replace if condition by > some arithmetics/ Maths. This is why I think assembly language should be mandatory in schools. :-) An if statement gets translated into something like (using a pseudo-assembly for readability): ;; if (b > 0) return a << b else return a >> -b compare b to 0 jump-less-than to L1 a := a << b jump L2 L1: b := -b a := a >> b L2: return ;; result in a It's the jump that's adding the time. But on an x86, that kind of instruction can be entirely cached and the Intel/AMD processors can perform predictive branching to speed up this bit of code. The only way you should be getting 20-50 times longer is if you aren't using any sort of optimizing run-time. Example: running always as byte code without compiling. But usually this kind of if-checking and bit-twiddling is so fast that it's not worth optimizing beyond a single statement. What are you coding that makes this the most expensive calculation in your program? OFF-TOPIC ========= Bonus Question: If branching is "20-50 times longer" than any of the operations (negation or shifting), how could you re-write this assembly to use a single branch statement? Extra Bonus: Using your favorite processor instruction set, come up with a fast implementation of: if (b > 0) return a << b; else return a >> -b;
Lew <noone@lewscanon.com> wrote: > On 04/26/2011 07:32 PM, Andreas Leitgeb wrote: >> Lew<noone@lewscanon.com> wrote: >>> Sanny, please attribute your citations. >>> Sanny wrote: [sic*] >>>>>>> Is there [...] >>> Eric Sosman wrote: [sic*] >>>>> Let me [...] >>> Sanny wrote: >>>> I didnt [...] >> *: Two of three attributions (intendly?) wrongly indented. >> Lew, please indent attributions with the correct number of ">"s. > Obviously you neglected to see how far back these quotes came. The > indentations were correct. Check again. I said they were wrongly *indented*, not that they were wrongly placed. As I explained already once, a snippet like this: Eric Sosman wrote: >> Let me [...] does NOT say, that the words "Let me" were Eric's, but instead implies, that Eric Sosman had quoted someone who wrote those words, because there are two levels difference in indentation. Had you instead written: > Eric Sosman wrote: >> Let me [...] it would have been correct and remained clear in further followups, each adding another ">" infront of all the lines (except the new initial attribution line). PS: there was another [sic] in my post, though: the word "intendedly" had unnoticedly lost one of its "ed"s. PPS: The higher the need to strictly clarify who wrote what, the lower really the use of contributing to that particular subthread. :-)
On 11-04-27 03:57 AM, Andreas Leitgeb wrote: [ SNIP ] > As I explained already once, a snippet like this: > > Eric Sosman wrote: > >> Let me [...] > > does NOT say, that the words "Let me" were Eric's, but instead implies, > that Eric Sosman had quoted someone who wrote those words, because there > are two levels difference in indentation. [ SNIP ] That's strictly true, but Jesus, I hope nobody does that. :-) I've seen a few too many flame wars start from attribution confusion caused by quoting finessing like that. AHS
On 4/26/2011 10:40 PM, Travers Naran wrote: .... > ;; if (b > 0) return a << b else return a >> -b > compare b to 0 > jump-less-than to L1 > a := a << b > jump L2 > L1: > b := -b > a := a >> b > L2: > return ;; result in a .... > It's the jump that's adding the time. But on an x86, that kind of > instruction can be entirely cached and the Intel/AMD processors can > perform predictive branching to speed up this bit of code. > > The only way you should be getting 20-50 times longer is if you > aren't using any sort of optimizing run-time. Example: running always > as byte code without compiling. > > But usually this kind of if-checking and bit-twiddling is so fast > that it's not worth optimizing beyond a single statement. What are > you coding that makes this the most expensive calculation in your > program? .... The obvious possibility is a random mix of left and right shifts, with the two directions equally probable. In that case, the hardware branch prediction would mis-predict, on average, half the time. When the hardware branch prediction gets it wrong, the result is a complete pipeline flush. With deep pipelines and multiple instructions in each pipeline stage, a pipeline flush costs the equivalent of dozens of simple arithmetic operations. My question is whether the measurement was from the actual program, or from a benchmark that may differ from the real program in ways that affect branch prediction. > If branching is "20-50 times longer" than any of the operations > (negation or shifting), how could you re-write this assembly to use a > single branch statement? Why bother? Your sample code only has one conditional branch, "jump-less-than to L1". Unconditional jumps to a fixed target, such as "jump L2" are always correctly predicted, and take about the same time as a simple arithmetic operation. The method is short enough that the JVM will in-line it anywhere it is frequently called so we don't have to worry about the return. Patricia
Andreas Leitgeb wrote: > Lew wrote: >> Andreas Leitgeb wrote: >>> Lew wrote: >>>> Sanny, please attribute your citations. >>>> Sanny wrote: [sic*] >>>>>>>> Is there [...] >>>> Eric Sosman wrote: [sic*] >>>>>> Let me [...] >>>> Sanny wrote: >>>>> I didnt [...] >>> *: Two of three attributions (intendly?) wrongly indented. >>> Lew, please indent attributions with the correct number of ">"s. >> Obviously you neglected to see how far back these quotes came. The >> indentations were correct. Check again. [Andreas] > I said they were wrongly *indented*, not that they were wrongly placed. > > As I explained already once, a snippet like this: > > Eric Sosman wrote: > >> Let me [...] > > does NOT say, that the words "Let me" were Eric's, but instead implies, > that Eric Sosman had quoted someone who wrote those words, because there > are two levels difference in indentation. TFB, dude. > Had you instead written: > > Eric Sosman wrote: > >> Let me [...] > it would have been correct and remained clear in further followups, > each adding another ">" infront of all the lines (except the new > initial attribution line). > > PS: there was another [sic] in my post, though: the word "intendedly" > had unnoticedly lost one of its "ed"s. > > PPS: The higher the need to strictly clarify who wrote what, the lower > really the use of contributing to that particular subthread. :-) Fuck that. I'm sticking with the indentation Thunderbird gives me, and the occasional reinforcement with reminders of whose speaking. Work it out or don't read it, I don't care which. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
Travers Naran wrote: > On 26/04/2011 9:32 AM, Sanny wrote: >> I have computed and found "if statments" take 20-50 times longer than >> basic arithmetic operations. So I wanted to replace if condition by >> some arithmetics/ Maths. > > This is why I think assembly language should be mandatory in schools. :-) I think assembly level died when hot spot, branch prediction, parallelism and deep pipelines came in. I will never forget the day when a compiler BEAT me :-( BugBear
Lew <noone@lewscanon.com> wrote: > TFB, dude. I wouldn't care a dime, either, if you weren't always so f'ing insisting on others following usenet conventions.
On 4/26/2011 6:47 AM, Lew wrote: > On 04/26/2011 07:34 AM, Eric Sosman wrote: >> On 4/26/2011 5:04 AM, Sanny wrote: >>>> Is there any way to avoid the if condition and do right shift and left >>>> shift using operators depending on shiftby is +ve or -ve? >>> >>> I used below technique but it gives error. >>> >>> divider=Math.pow(2,shiftby); >>> then >>> output = (long) N / divider; >> >> Let me get this straight: You're worried about the inefficiency >> of an `if' that chooses between a left or a right shift, so you plan >> to eliminate the `if' by evaluating an exponential function? >> >> ARE YOU OUT OF YOUR MIND? > > Especially given that shift is blazingly efficient on just about any > computer that supports Java. You're optimizing something that's used > *as* an optimization, Sanny-Boy. As far as I can tell, Lew-Boy, he has not asked to optimize out the shift, except as a means to the end of avoiding a conditional branch. Whether that is an issue or not depends on the context, the predictability of the branch, and the performance of the alternatives. [I had not previously seen appending "-Boy" to the name as a convention for addressing people in USENET articles, but I'll go along with whatever mode of address the person I'm responding to seems to prefer.] Patricia
Patricia Shanahan wrote: > Lew wrote: > As far as I can tell, Lew-Boy, ... > > [I had not previously seen appending "-Boy" to the name as a convention > for addressing people in USENET articles, but I'll go along with > whatever mode of address the person I'm responding to seems to prefer.] It's an informal mode of address popular in the U.S. It rhymes with "Danny Boy", title the famous song set to an English folk tune. It's a rubric often used between friends, as in, "Hey, Jimmy-Boy! How the hell have you been, you old so-and-so?" I suppose you're complaining that I was being too informal. Sorry. You, of course, Dr. Shanahan, do not have to ask for the privilege of being informal with me. I would be honored to have you call me "Lew-Boy". -- Lew I am known as "Mr. Boy." I fetch and carry, wrap wires, do useful things around.
On 04/27/2011 10:03 AM, Andreas Leitgeb wrote: > Lew<noone@lewscanon.com> wrote: >> TFB, dude. > > I wouldn't care a dime, either, if you weren't always so > f'ing insisting on others following usenet [sic] conventions. You mean like actually attributing citations and providing enough useful information about a problem that someone could help them? Yeah, those are pretty fucking arbitrary conventions. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On Apr 27, 7:49=A0pm, Lew <no...@lewscanon.com> wrote: .... > It's an informal mode of address popular in the U.S. =A0It rhymes with "D= anny > Boy", title the famous song set to an English folk tune. =A0It's a rubric= often > used between friends, as in, "Hey, Jimmy-Boy! =A0How the hell have you be= en, you > old so-and-so?" Describing "Londonderry Air" as an _English_ folk tune could get you into troubles [sic]. P.S. I didn't realise your use of "-Boy" was just informal friendliness. I'd assumed you used it as a mild insult. Is that not the case?
Paul Cager wrote: > Lew wrote: >> ... "DannyBoy", title [of] the famous song set to an English folk tune. ... > Describing "Londonderry Air" as an _English_ folk tune could get you > into troubles [sic]. Good catch! My boo-boo. Me Oirish ancestors'd take a shillelagh to me for that error. -- Lew
On Tue, 26 Apr 2011 09:49:24 -0400, Lew <noone@lewscanon.com> wrote, quoted or indirectly quoted someone who said : >You claim inefficiency in something you have no clue whatsoever to be inefficient. If you examined the code generated, you might be pleasantly surprised. I did a fair bit of looking at the code Jet generated and came to the conclusion it would nearly always generate better code than a human would. It was not only optimising cycles, it was optimising pipelines. -- Roedy Green Canadian Mind Products http://mindprod.com Politicians complain that Kindles and iBooks are killing jobs by destroying the paper book industry. I see it that they have create a way to produce books for less than a third the cost without destroying forests and emitting greenhouse gases in the process. They have created wealth. They are encouraging literacy and cutting the costs of education.
On 04/27/2011 10:25 PM, Roedy Green wrote: > On Tue, 26 Apr 2011 09:49:24 -0400, Lew<noone@lewscanon.com> wrote, > quoted or indirectly quoted someone who said : > >> You claim inefficiency in something you have no clue whatsoever to be inefficient. > > If you examined the code generated, you might be pleasantly surprised. > I did a fair bit of looking at the code Jet generated and came to the > conclusion it would nearly always generate better code than a human > would. It was not only optimising cycles, it was optimising pipelines. Excellent point. Hotspot also optimizes code to a good level due to its dynamic nature. I don't know how to examine its results, although that would be interesting to capture somehow. -- Lew Honi soit qui mal y pense. http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
On 2011-04-27 08:34:32 -0400, Patricia Shanahan said: > On 4/26/2011 10:40 PM, Travers Naran wrote: > ... >> ;; if (b > 0) return a << b else return a >> -b >> compare b to 0 >> jump-less-than to L1 >> a := a << b >> jump L2 >> L1: >> b := -b >> a := a >> b >> L2: >> return ;; result in a > ... >> It's the jump that's adding the time. But on an x86, that kind of >> instruction can be entirely cached and the Intel/AMD processors can >> perform predictive branching to speed up this bit of code. >> >> The only way you should be getting 20-50 times longer is if you >> aren't using any sort of optimizing run-time. Example: running always >> as byte code without compiling. >> >> But usually this kind of if-checking and bit-twiddling is so fast >> that it's not worth optimizing beyond a single statement. What are >> you coding that makes this the most expensive calculation in your >> program? > ... > > The obvious possibility is a random mix of left and right shifts, with > the two directions equally probable. In that case, the hardware branch > prediction would mis-predict, on average, half the time. There are worse distributions. Consider a program that alternates between the two possible branch outcomes, assuming a four-bit branch prediction counter like those found in several generations of Intel chips: it's possible that the sequence will start by acting opposite to the prediction and flipping the predicted direction for the next branch (from b01 to b10 or vice versa). A strictly alternating sequence of branches would then be mis-predicted *every time*. One of the things that could've made Itanic so cool was the ability to pre-emptively evaluate both sides of a branch, many instructions in advance, and throw away all the alternatives but the one that "actually happened". Unfortunately, programming around this was really hard even for experienced compiler writers, and the chips were notoriously power-hungry and expensive, so it never really took off. > When the hardware branch prediction gets it wrong, the result is a > complete pipeline flush. With deep pipelines and multiple instructions > in each pipeline stage, a pipeline flush costs the equivalent of dozens > of simple arithmetic operations. > > My question is whether the measurement was from the actual program, or > from a benchmark that may differ from the real program in ways that > affect branch prediction. My question is "who cares?" There are lots of ways to squeeze more performance out of an otherwise-optimal algorithm: make better use of vector operations, migrate some or all of the work to the GPU (a massively-parallel floating point unit), or find ways to avoid running it at all. Measuring the cost of an if statement is pretty far down the list of tuning choices. (Having seen examples of Sanny's code in other newsgroups, I am extremely doubtful that he's reached the "optimal algorithm" stage. However, I haven't seen his code, so it's possible.) >> If branching is "20-50 times longer" than any of the operations >> (negation or shifting), how could you re-write this assembly to use a >> single branch statement? > > Why bother? Your sample code only has one conditional branch, > "jump-less-than to L1". Unconditional jumps to a fixed target, such as > "jump L2" are always correctly predicted, and take about the same time > as a simple arithmetic operation. Unless they force a cache stall. For a routine as trivial as the one Travers posted, it's unlikely that the final 'return' would be on a separate cache line from the start of the routine, but in a longer routine, replacing the jump-to-return with a return might actually keep the end of the routine out of cache. Of course, if the code that called this routine has fallen out of cache, the return instruction will force a cache stall, instead. > The method is short enough that the > JVM will in-line it anywhere it is frequently called so we don't have to > worry about the return. Agree. Even though it's not actually magic and doesn't always produce totally optimal (either in time or in space) code, the JIT compiler produces surprisingly good code most of the time. Second-guessing it down at the level of individual machine instructions is the sort of thing that impresses bystanders but rarely accomplishes anything useful. -o
Travers Naran wrote: > The usual rules for optimization: > > 1. Profile your code > 2. Determine where your code is spending most of its time > 3. Re-visit your algorithm and decide if you are using the right algorithm. > 3a. If so, optimize the methods that are consuming most of the time. > 3b. Implement a better algorithm 3c Run your testcases to check that nothing is broken 3d Realize that you haven't one 3e Roll back your changes using SVN->Revert 3f Write a testcase checking the current algorithm and its borders where it's not working anymore and run it 3g Go back to 3b and skip 3d - 3g 3f > and repeat these processes. Regards, Lothar -- Lothar Kimmeringer E-Mail: spamfang@kimmeringer.de PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81) Always remember: The answer is forty-two, there can only be wrong questions!
On 4/27/2011 9:37 PM, Owen Jacobson wrote: > On 2011-04-27 08:34:32 -0400, Patricia Shanahan said: .... >> The obvious possibility is a random mix of left and right shifts, with >> the two directions equally probable. In that case, the hardware branch >> prediction would mis-predict, on average, half the time. > > There are worse distributions. Consider a program that alternates > between the two possible branch outcomes, assuming a four-bit branch > prediction counter like those found in several generations of Intel > chips: it's possible that the sequence will start by acting opposite to > the prediction and flipping the predicted direction for the next branch > (from b01 to b10 or vice versa). A strictly alternating sequence of > branches would then be mis-predicted *every time*. .... I agree that, depending on the branch predictor implementation, it is possible to get worse than 50% mis-prediction for a single conditional branch. However, the right patterns are relatively unlikely. On the other hand, someone who does not understand branch prediction would be quite likely write a conditional branch benchmark that gets 50% mis-prediction. Patricia
Owen Jacobson wrote: > > One of the things that could've made Itanic so cool was the ability to > pre-emptively evaluate both sides of a branch, many instructions in > advance, and throw away all the alternatives but the one that "actually > happened". Unfortunately, programming around this was really hard even > for experienced compiler writers, and the chips were notoriously > power-hungry and expensive, so it never really took off. Eh? Speculative execution is hardly a rare CPU feature, among modern general-purpose CPUs. At least one reference[1] claims "all modern CPUs" have spec-exec - which seems dubious, but I suppose one could quibble over what a "modern" CPU is. x86 CPUs have had it at least since the Pentium Pro (P6).[2] PPC has had it since at least the 603.[3] If it's branch predication (note I'm talking about *predication*, not *prediction*, here) you're thinking of, that also antedates Itanium and continues to be implemented in modern CPUs. DEC Alpha and HP PA-RISC had limited predication, where stores to memory on a speculative branch could be rewritten to write to a register instead, with a predicate-controlled store after the branch result was known; and PPC has had aggressive predication since at least the 604.[4] US patent 5,471,593 describes predicated execution; it was filed in 1995. And it cites prior work, including the Cydra 5 from the late '80s - which I don't know much about, but which apparently had a basic predicated-execution system. So, not new in the Itanium, and not sinking with it either. [1] http://www.hardwaresecrets.com/printpage/209 [2] http://www.datasheetarchive.com/datasheet-pdf/078/DSAE0072944.html [3] http://www.cs.pitt.edu/~alanjawi/history.html [4] http://www.princeton.edu/~rblee/ELE572Papers/the-effects-of-predicated.pdf -- Michael Wojcik Micro Focus Rhetoric & Writing, Michigan State University
On 27.04.2011 07:40, Travers Naran wrote: > On 26/04/2011 9:32 AM, Sanny wrote: >> I have computed and found "if statments" take 20-50 times longer than >> basic arithmetic operations. So I wanted to replace if condition by >> some arithmetics/ Maths. > > This is why I think assembly language should be mandatory in schools. :-) > > An if statement gets translated into something like (using a > pseudo-assembly for readability): > > ;; if (b > 0) return a << b else return a >> -b > compare b to 0 > jump-less-than to L1 > a := a << b > jump L2 > L1: > b := -b > a := a >> b > L2: > return ;; result in a Folks, this is all too complicated. As already stated, branches can kill the performance, but it is just too easy without them: (x >> r) << l. And set l = max(-s,0) and r = max(s,0) where is is the "signed right shift". If the shift is always by the same constant, it is easier to precalculate l and r once and apply the shift all over again. Alternatively, if the shift is always dynamic, l and r can also be computed without any branch: int m = (s >> 31); int r = s & m; int l = (-s) & (~m); int x = (x >> r) << l; Whether this is faster depends of course whether a branch prediction is able to predict the branches well. Greetings, Thomas