Java left shift and right shift operators.

[Sanny]

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]

 

[Lothar Kimmeringer]

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: (e-mail address removed)
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!

 

[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=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]

 

[Eric Sosman]

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?

 

[Joshua Cranmer]

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.

 

[Lew]

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]

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?

 

[Travers Naran]

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...

 

[Travers Naran]

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.

 

[Lew]

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]

Please follow Java naming conventions.

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]

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.

 

[Martin Gregorie]

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.

 

[Sanny]

This is a conversation, not a bunch of lackeys leaping to your bid.  Please

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 inefficient.

Here's another question, assuming you answer Lothar's question at all, ifyou
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

 

[Sanny]

Is there any way to avoid the if condition and do right shift and left

     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.

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

 

[Sanny]

Doesn't matter, the Java operator *is* defined for negative values.

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.

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

 

[Lew]

Sanny, please attribute your citations.

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]

... java [psic] ...

self-[sic]

 

[Lew]

Sanny, please attribute your citations.

See? You didn't write that.

Lew 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.

 

[Daniele Futtorovic]

"'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.