f

Java left shift and right shift operators.

```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]

```
 0
4/26/2011 7:38:12 AM
comp.lang.java.programmer 52711 articles. 1 followers.

46 Replies
928 Views

Similar Articles

[PageSpeed] 52

```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!
```
 0
news200709 (193)
4/26/2011 7:55:03 AM
```> 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);

binary Value:
111111111111111111111111111111111111111111111111111111111111111

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]
```
 0
4/26/2011 9:04:23 AM
```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

```
 0
pats (3556)
4/26/2011 10:16:45 AM
```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
```
 0
esosman2 (3096)
4/26/2011 11:34:27 AM
```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
```
 0
Pidgeot18 (1520)
4/26/2011 12:41:30 PM
```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.

--
Lew
Honi soit qui mal y pense.
```
 0
noone7 (4050)
4/26/2011 1:47:06 PM
```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

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.
```
 0
noone7 (4050)
4/26/2011 1:49:24 PM
```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.
>
> 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...
```
 0
tnaran1 (22)
4/26/2011 2:09:53 PM
```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;

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:

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.
```
 0
tnaran1 (22)
4/26/2011 2:30:38 PM
```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.
```
 0
noone7 (4050)
4/26/2011 3:21:23 PM
```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);

>> then
>> output = (long) N / divider;

> 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.
```
 0
noone7 (4050)
4/26/2011 3:24:31 PM
```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.
```
 0
noone7 (4050)
4/26/2011 3:35:38 PM
```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       |
```
 0
martin1645 (571)
4/26/2011 3:37:27 PM
```> This is a conversation, not a bunch of lackeys leaping to your bid. =A0Pl=
ease

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

```
 0
4/26/2011 4:32:02 PM
```> >> 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
```
 0
4/26/2011 4:39:05 PM
```> > 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
```
 0
4/26/2011 4:46:39 PM
```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
```
 0
pats (3556)
4/26/2011 6:09:22 PM
```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
```
 0
pats (3556)
4/26/2011 6:17:31 PM
```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

[1]
<http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.2.1>

[2]

--
Lew
Honi soit qui mal y pense.
```
 0
noone7 (4050)
4/26/2011 6:55:14 PM
```Lew wrote:
>> ... java [psic] ...

self-[sic]

--
Lew
Honi soit qui mal y pense.
```
 0
noone7 (4050)
4/26/2011 6:57:09 PM
```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.

RTFM.  RTFM.  RTFM.  RTFM.  RTFM.

--
Lew
Honi soit qui mal y pense.
```
 0
noone7 (4050)
4/26/2011 7:02:03 PM
```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"
```
 0
da.futt.news (247)
4/26/2011 7:38:36 PM
```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/
```
 0
shortcutter (5830)
4/26/2011 8:06:55 PM
```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
```
 0
pats (3556)
4/26/2011 8:09:34 PM
```Lew <noone@lewscanon.com> wrote:
> Sanny wrote: [sic*]
>>>>> Is there [...]
> Eric Sosman wrote: [sic*]
>>> Let me [...]
> Sanny wrote:
>> I didnt [...]

*: Two of three attributions (intendly?) wrongly indented.

```
 0
avl1 (2748)
4/26/2011 11:32:15 PM
```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.

sorry, that's *way* too obvious, there must be a grue waiting for

> 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
```
 0
esosman2 (3096)
4/27/2011 1:14:48 AM
```On 04/26/2011 07:32 PM, Andreas Leitgeb wrote:
> Lew<noone@lewscanon.com>  wrote:
>> Sanny wrote: [sic*]
>>>>>> Is there [...]
>> Eric Sosman wrote: [sic*]
>>>> Let me [...]
>> Sanny wrote:
>>> I didnt [...]
>
> *: Two of three attributions (intendly?) wrongly indented.
>

Obviously you neglected to see how far back these quotes came.  The
indentations were correct.  Check again.

--
Lew
Honi soit qui mal y pense.
```
 0
noone7 (4050)
4/27/2011 4:08:24 AM
```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

;; 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;
```
 0
tnaran1 (22)
4/27/2011 5:40:35 AM
```Lew <noone@lewscanon.com> wrote:
> On 04/26/2011 07:32 PM, Andreas Leitgeb wrote:
>> Lew<noone@lewscanon.com>  wrote:
>>> Sanny wrote: [sic*]
>>>>>>> Is there [...]
>>> Eric Sosman wrote: [sic*]
>>>>> Let me [...]
>>> Sanny wrote:
>>>> I didnt [...]
>> *: Two of three attributions (intendly?) wrongly indented.
> 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.

> 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

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. :-)
```
 0
avl1 (2748)
4/27/2011 6:57:54 AM
```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
```
 0
4/27/2011 10:00:30 AM
```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

Patricia

```
 0
pats (3556)
4/27/2011 12:34:32 PM
```Andreas Leitgeb wrote:
> Lew wrote:
>>  Andreas Leitgeb wrote:
>>> Lew  wrote:
>>>> Sanny wrote: [sic*]
>>>>>>>> Is there [...]
>>>> Eric Sosman wrote: [sic*]
>>>>>> Let me [...]
>>>> Sanny wrote:
>>>>> I didnt [...]
>>> *: Two of three attributions (intendly?) wrongly indented.
>> 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.

>     >  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
>
> 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.
```
 0
noone7 (4050)
4/27/2011 12:42:41 PM
```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
```
 0
bugbear (609)
4/27/2011 1:28:24 PM
```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.

```
 0
avl1 (2748)
4/27/2011 2:03:29 PM
```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
```
 0
pats (3556)
4/27/2011 4:23:08 PM
```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.
```
 0
noone7 (4050)
4/27/2011 6:49:29 PM
```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.
```
 0
noone7 (4050)
4/27/2011 6:54:53 PM
```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?
```
 0
paul.cager (69)
4/28/2011 12:28:13 AM
```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
```
 0
noone7 (4050)
4/28/2011 2:06:16 AM
```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.

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

```
 0
see_website (5876)
4/28/2011 2:25:41 AM
```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.
```
 0
noone7 (4050)
4/28/2011 3:08:16 AM
```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

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

```
 0
angrybaldguy (338)
4/28/2011 4:37:25 AM
```Travers Naran wrote:

> The usual rules for optimization:
>
> 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!
```
 0
news200709 (193)
4/28/2011 7:14:32 AM
```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

```
 0
pats (3556)
4/28/2011 11:02:04 PM
```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
```
 0
mwojcik (1879)
4/28/2011 11:22:58 PM
```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
>
> ;; 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
```
 0
thor16 (336)
4/29/2011 10:02:15 PM

Similar Artilces:

Left Shift / Right Shift Operators
Hi, Is there any way to catch the losing bit occurring due to Right Shift Operator ? e.g int a = 5 ; a = a >> 1 ; // // a is now 2 and the least significant bit is lost // // I want this solution for the question: "How to find if the number is even or odd using only "<<" or/and ">>" operators ?" On Thu, 29 Nov 2006, Santosh Nayak wrote: > > Is there any way to catch the losing bit occurring due to Right Shift > Operator ? int a = 5; int lost_bit = a & 1; a = a >> 1; /* now lost_bit holds the lost bit */ > ...

Skybuck presents ShiftLeft( Left, Right, Shift ) and ShiftRight( Right, Left, Shift )
Hello, I think these two functions will come in very handy to solving the "write longword bits" problem. ShiftLeft( Left, Right, Shift ) ShiftRight( Right, Left, Shift ) Shifting with extra inputs is what is required to solve it nicely. // Begin of Code *** program Project1; {\$APPTYPE CONSOLE} { Skybuck presents ShiftLeft( Left, Right, Shift ) and ShiftRight( Right, Left, Shift ) version 0.01 created on 5 may 2008 by Skybuck Flying. Be carefull though, the shift parameter must be 0 to 31. } uses SysUtils; // make overloaded versions for easy coding // display in big e...

shift left, shift right
Hello, Is there any command to shift left or right a vector ? thanks for your reply. patrice: <SNIP ...Is there any command to shift left or right a vector... a hint: help circshift us Try these: 4.1 Vectors To shift and rotate the elements of a vector, use X([ end 1:end-1 ]); % shift right/down 1 element X([ end-k+1:end 1:end-k ]); % shift right/down k elements X([ 2:end 1 ]); % shift left/up 1 element X([ k+1:end 1:k ]); % shift left/up k elements Try this link: <http://www.cs.huji.ac.il/course/2003/impr/matlab/MatlabTip.pdf> -TRO patrice wrote: > > > H...

what does SHIFT-left-or-right of up-down-left-right do?
Well, I know about shift up-and-down: shift-right ("red" or whatever) up and down on choose-box, HIST, things like that, take the cursor all the way to the beginning or the end. shift-left ("white") on up and down scroll the screen-full up or down (the FIRST such click *stupidly* goes to the final CURRENTLY-ON-SCREEN choice or whatever (meaning TWO double-button-pushes to scroll-down that FIRST time.) What are some of the OTHER possibilities, ie with the left and right arrows? Oh, apparantely undocumented, I&#...

left shift then right shift an unsigned int
Hello, for the following code: unsigned int var = 0xFF2277F0UL; unsigned char take2 = (var << 8) >> 24; Is there any pitfall about the shift? (get '22' i.e. 34 or '"' as wanted) Thanks and best regards, Wenjie On 11 Jul 2003 04:07:43 -0700, gokkog@yahoo.com (Wenjie) wrote: >Hello, for the following code: > unsigned int var = 0xFF2277F0UL; > unsigned char take2 = (var << 8) >> 24; >Is there any pitfall about the shift? (get '22' i.e. 34 or '"' as wanted) It looks OK to me... -- Bob Hairg...

Distinguish Shift - click left and Shift
Is there a way to distinguish the SelectionType property in a figure for a Shift - click left and Shift - click right? Both result in the SelectionType 'Extend'... Thx "Stefan" <s@m.de> wrote in message <hpkik9\$5c3\$1@fred.mathworks.com>... > Is there a way to distinguish the SelectionType property in a figure for a Shift - click left and Shift - click right? > Both result in the SelectionType 'Extend'... > > Thx Hi Stefan, if you are in a callback function you can use this example with small changes, taken from the figure prope...

java.lang.ExceptionInInitializerError: java.lang.ArrayIndexOutOfBoundsException
Hi, I am new to DB2. I am getting this error while loading the DB2Driver. I don't have any idea about where i might have gone wrong. please help me. Below is the stack trace. Stack Trace: java.lang.ExceptionInInitializerError: java.lang.ArrayIndexOutOfBoundsException at COM.ibm.db2.jdbc.app.DB2Driver.SQLAllocEnv(Native Method) at COM.ibm.db2.jdbc.app.DB2Driver.<init>(DB2Driver.java:245) at COM.ibm.db2.jdbc.app.DB2Driver.<clinit>(DB2Driver.java:130) at java.lang.Class.forName0(Native Method) at java.lang.Class.forName(Cla...

Java Java
Have my first Open Source Linux Java Project. Working on a second right now. Coming out with a distro called OPEN*WINDOWS. It will be at www.black-and-company.com tab wrote: > Have my first Open Source Linux Java Project. > Working on a second right now. > > Coming out with a distro called OPEN*WINDOWS. > > It will be at www.black-and-company.com > Wasn't that the whole point of Lindows? Oh, right, we didn't care for that either. tab wrote: > Have my first Open Source Linux Java Project. > Working on a second right now. > > Coming out with a ...

Java in Java
Is it possible to download a Java app (applet etc?) and run it inside a desktop Java app? -- Dirk http://www.transcendence.me.uk/ - Transcendence UK http://www.theconsensus.org/ - A UK political party http://www.onetribe.me.uk/wordpress/?cat=5 - Our podcasts on weird stuff Dirk Bruere at NeoPax wrote: > Is it possible to download a Java app (applet etc?) and run it inside a > desktop Java app? > Quite likely, but you won't necessarily get the same security model, unless you were careful about it. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/&g...

java.lang.StringIndexOutOfBoundsException: String index out of range: 23 at java.lang.String.charAt(String.java:460)
Hi All I am having the torque3.1.jar and postgresql-7.4. I have compiled the new jdbc driver called as postgresql.jar and have placed it in the lib directory from where the ant scripts catch the jars. Whenever i try to access through torque gestList = BaseGestlistPeer.doSelect(new Criteria()); this error arises java.lang.StringIndexOutOfBoundsException: String index out of range: 23 at java.lang.String.charAt(String.java:460) at org.postgresql.jdbc2.ResultSet.toTimestamp(ResultSet.java:1653) at org.postgresql.jdbc2.ResultSet.getTimestamp(ResultSet.java...

How to do >>(right shift) and <<(left shift) in Matlab?
Hi all, How >>(right shift) and <<(left shift) 2'complement number (both positive and negative integer). Is x>>2 equal to floor(x/4)? And is x<<2 equal to x*4? Best regards, Davy Soho wrote: > Hi all, > > How >>(right shift) and <<(left shift) 2'complement number > (both positive and negative integer). > > Is x>>2 equal to floor(x/4)? > > And is x<<2 equal to x*4? > > Best regards, > Davy > Does bitshift: http://www.mathworks.com/access/helpdesk/help/techdoc/ref/bitshift.html do what you wa...

left and right shift operations for custom menus
Hi everyone I want to create a custom menu on my HP50g. Reading the electronic user's guide I see that to create a (permanent) custom menu that assigns the functions EXP, LN, GAMMA and ! to the keys F1, F2, F3 and F4 respectively, one enters: {EXP LN GAMMA !} ENTER MENU However a little later in the guide it states that the general form of the list above is: {=93label1=94, function1, ls1, rs1}, {=93label2=94, function2, ls2, rs2},= =85} where "label1" is the name of the soft menu key, funtion1 is the function that will be carried out when the key is pressed and ls1 and rs1 ...

Precision of C++ left/right shift operator..
I am using this type of code to do right-shifting, B = 3; data1 = (data + (1 << (B-1))) >> B; data1 seems incorrect when data = -4-8*i.. which means it rounds -1.5 to -1 instead of -2. On the positive side, 1.5 is rounded to 2, which ic correct. For left-shift, it's simply as follows, no pitfalls, am I right? data1 = data << B; Thanks. G Iveco wrote: > I am using this type of code to do right-shifting, > > B = 3; > data1 = (data + (1 << (B-1))) >> B; > > data1 seems incorrect when data = -4-8*i.. which means it > rounds -1.5 to...

java.lang.Set with elements of type java.lang.Set
Roughly I do something along the lines of: Set set = new HashSet(); Set elem = new HashSet(); set.add(elem); // now we change the elem and add it again to the set elem.add(some object here); set.add(elem); I found out the hard way that 'set' may now contain 'elem' either once or twice, the reason being that 'elem.add()' changes the hashCode of elem such that it is not noticed that it is in 'set' already on the 2nd 'set.add()'. Question: What I would actually want is an IdentityHashSet() set = new IdentityHashSet() but this does not...

to use import java.lang.* or import java.lang.Math or none at all?
Hi guys, i knew that by default all java.lang classes will be imported by the compiler during compilation. but, to make it easier for the computer, should i specify which class i really will be using? does this action will boost the performance during compilation and runtime or not a matter at all? the answer to this post will definitely affect my programming style in the future when i'm considering "to import or not to import"... hmm,,, thanks in advance. JPractitioner wrote: > i knew that by default all java.lang classes will be imported by the > compiler during compilation. but, to make it easier for the computer, > should i specify which class i really will be using? does this action > will boost the performance during compilation and runtime or not a > matter at all? Whether and how you import classes has exactly zero effect at runtime. Imports (with or without wildcards) are only a kind of abbreviation provided by the compiler to save us the effort of typing in fully-qualified type names every time. In theory explicit importing should make compilation faster -- by a very tiny amount. I've never heard anyone claim that they've even managed to measure a difference let alone found a case where it made a practical difference. So the question comes down to how to write your code for maximum clarity. One school of thought asserts that you should always import each class explicitly (rather than by a wildcard). There's a fai...

Error occurred during initialization of VM java/lang/NoClassDefFoundError: java/lang/Object
I downloaded jdk-6u7-solaris-sparcv9.tar.Z and installed it by these commands: # zcat jdk-6u7-solaris-sparc.tar.Z | tar -xf - # pkgadd -d . SUNWj6rtx SUNWj6dvx SUNWj6dmx # /usr/jdk/instances/jdk1.6.0/bin/sparcv9/java -version Error occurred during initialization of VM java/lang/NoClassDefFoundError: java/lang/Object # ls /usr/jdk/instances/ jdk1.5.0 jdk1.6.0 # uname -a SunOS sun1 5.10 Generic sun4u sparc SUNW,Sun-Blade-2500 Please help to fix the error. Thanks. TsanChung wrote: > I downloaded jdk-6u7-solaris-sparcv9.tar.Z and installed it by these > commands: > # zcat jdk-6u7-so...

Error occurred during intialization of VM java/lang/NoClassDefFoundError: java/lang/Object
Good day to all, I have installed the j2se/netbeans binary bundle on red hat 9. I can run everything perfectly as root but when I try to compile with any other user I get: Error occurred during intialization of VM java/lang/NoClassDefFoundError: java/lang/Object When I saw this it seemed like a permissions problem but I checked the permissions and everything seemed fine. All users have execute permissions of javac and java. I have read other threads dealing with the same or similar problem but have not reached any solution yet. I would appreciate if anyone that has run into this type o...

java.lang vs java.util
Surprising to see something defined in java.lang <http://developer.android.com/reference/java/lang/Iterable.html> depend on something defined in java.util <http://developer.android.com/reference/java/util/Iterator.html>. Surely the hierarchy should go the other way? On 4/1/2011 9:11 PM, Lawrence D'Oliveiro wrote: > Surprising to see something defined in java.lang > <http://developer.android.com/reference/java/lang/Iterable.html> depend on > something defined in java.util > <http://developer.android.com/reference/java/util/Iterator.html>. > > Surely the hierarchy should go the other way? I think Iterable may make it into java.lang because of its significance in the foreach statement. Patricia On 04/02/2011 12:23 AM, Patricia Shanahan wrote: > On 4/1/2011 9:11 PM, Lawrence D'Oliveiro wrote: >> Surprising to see something defined in java.lang >> <http://developer.android.com/reference/java/lang/Iterable.html> depend on >> something defined in java.util >> <http://developer.android.com/reference/java/util/Iterator.html>. >> >> Surely the hierarchy should go the other way? Not if it wants to be consistent with http://download.oracle.com/javase/6/docs/api/ don't'cha think? And the so-called "hierarchy" of java.util and java.lang is that they are equal. The language reserves for itself the entire panoply of java.* and javax.* packages. > I think It...

modifying java.lang.String.java
Hi, I'm trying to modify java.lang.String.java and add the modified String.class to rt.jar [THIS IS FOR MYSELF ONLY AND WILL NOT BE DEPLOYED]. I cannot add "private final boolean tainted[] = new boolean[5];" to String.java. If I do, it still compiles and I can add it to rt.jar and compile a test program against it. However, the JVM crashes with a strange message: java.lang.IllegalArgumentException: name can't be empty at java.security.BasicPermission.init(Unknown Source) at java.security.BasicPermission.<init>(Unknown Source) at java....

Poll: Is a Java Method an Instance of the Java Class java.lang.reflect.Method? Please reply with YES or NO.

shift right operator
main() { int a =100; a = a>>32; printf(" %d", a); } it prints "a" as 100 only....but I am expecting a = 0..... can some one tell me the reason? bye Deepak\ DeepaK K C wrote: > main() > { > int a =100; > a = a>>32; > printf(" %d", a); > } > > it prints "a" as 100 only....but I am expecting a = 0..... > can some one tell me the reason? It's a manifestation of undefined behaviour. (Some machines only have a 5-bit shift count, for example.) What happens if you turn your compiler warnings up? -- Chris "...

CheckBox in Column of JTable: Exception: java.lang.String cannot be cast to java.lang.Boolean
Hello, I have discovered a hidden error. My project was working for awhile, but then I started to get the below error. My error comes from the fact that I'm using a checkbox in a jtable, and I'm using the below "getColumnClass". Thank you, compile: run: Exception in thread "AWT-EventQueue-0" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Boolean at javax.swing.JTable\$BooleanRenderer.getTableCellRendererComponent(JTable.java:5412) at javax.swing.JTable.prepareRenderer(JTable.java:5735) at javax.swing.plaf.basic.BasicTableU...

java.lang.NoClassDefFoundError: java.lang.NoClassDefFoundError: org/apache/commons/logging/LogFactory
Hi, I'm trying to use the httpclient within Jython (see http://jakarta.apache.org/commons/httpclient/ for more information on the httpclient). My Jython version is: Jython 2.1 on java1.4.2_04 (JIT: null) My Java version is: java version "1.4.2_04" Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_04-b05) Java HotSpot(TM) Client VM (build 1.4.2_04-b05, mixed mode) My CLASSPATH includes: jdom.jar xerces.jar jython.jar jt400.jar log4j-1.2.8.jar commons-httpclient-2.0.jar When I just try to perform the import statements from example code I get the error pasted below....

Error occurred during initialization of VM java/lang/NoClassDefFoundError: java/lang/Object (ant/tomcat/spring)
Hi, I've been trying to get Spring working with ant and tomcat. Ant was building just fine, but I came in today and tried to build it and got this: Error occurred during initialization of VM java/lang/NoClassDefFoundError: java/lang/Object ?!?! Makes no sense to me. There _is_ an older version of java installed on my machine; but JAVA_HOME and ANT_HOME are set to the correct paths, and <which java>and <java -version> produce the correct version. Any help would greatly alleviate my frustration! Thanks in advance... Courtney ...

Web resources about - Java left shift and right shift operators. - comp.lang.java.programmer

Operator - Wikipedia, the free encyclopedia
Text is available under the Creative Commons Attribution-ShareAlike License ;additional terms may apply. By using this site, you agree to the ...

Horse-drawn carriage operator filmed hurling violent threats and racial abuse
Melbourne's angriest carriage driver appears to have again been caught on camera venting his spleen, this time hurling racial abuse and violent ...

ACT believes existing laws adequate to prevent 'gay cure' operators
The territory government says it will watch Victoria's push to crack down on 'gay conversion therapy', but believes the practice is prevented ...

Horse-drawn carriage operator filmed hurling violent threats and racial abuse
[ The Age - Text-only index ] Horse-drawn carriage operator filmed hurling violent threats and racial abuse Date: February 18 2016 Patrick Hatch ...

Low loonie a 'silver lining' for province's tourism operators
Several industries in Newfoundland and Labrador are seeing a silver lining in the low Canadian dollar, including the province's tourism operators. ...

Luge track operator likely not liable for teenagers' deaths: lawyer
It is unlikely the operator of a high-performance training facility in Calgary would be held legally responsible for the deaths of two teenage ...

Why Mars Is America's Biggest Veterinary Operator - CMO Strategy - AdAge
Search, social, and programmatic display advertising has gone mobile. Thanks to smartphones, calls from marketing are skyrocketing. Learn new ...

Ex-Alaska medevac operator tells jury of encounters with defendant in fraud cause
At the start, before Mark Avery’s spectacular fall from his Anchorage aviation empire, he was working with a medevac operator and pilot who had ...

Drone operator unwittingly films new Top Gear shoot
Filed under: TV/Movies , Videos , Ford , Driving , UK A Scotsman driving through the Highlands stumbled on a new Top Gear shoot and filmed it ...

Mobile operator Three to block ads at the network level
... with advertisers recently too and is looking to discover just why people block ads on the web . In an interesting move, mobile network operator ...

Resources last updated: 2/21/2016 10:24:44 PM