«

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:
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:
11111111111111111111111111111111111111111111111111 1111111111111

While correct answer is :
10000000000000000000000000000000000000000000000000 00000000000000

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

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<<1;
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/wikipedi.../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/wikipedi.../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/wikipedi.../c/cf/Friz.jpg