binary algorithm

[shana07]

I do really need to consult you guys about java codes.
Please give me some pointer where should I refer regarding 'binary concept' especially when it does involve with such this '>>'.
What does it mean or to say in word?

Below I paste codes for binary gdc computation....please advise...many thanks.

private static long binaryAlgorithm (long u, long v) 
 {
                 long gcd = 0;
        long k = 0;
        long t = 0;
 
        u = Math.abs (u);
        v = Math.abs (v);
        // Find power of 2
        while (true) 
        {
          if (isOdd (u)) 
          {
            break;
          }
 
          if (isOdd (v)) 
          {
            break;
          }
          k++;
          u = u >> 1;
          v = v >> 1;          
        }

[JosAH]

I ripped this straight from the JLS Java Language Specification. Here goes:

The shift operators include left shift <<, signed right shift >>, and unsigned right
shift >>>; they are syntactically left-associative (they group left-to-right). The
left-hand operand of a shift operator is the value to be shifted; the right-hand
operand specifies the shift distance.

The type of each of the operands of a shift operator must be a type that is
convertible to a primitive integral type, or a compile-time error occurs. Binary
numeric promotion is not performed on the operands; rather, unary numeric
promotion is performed on each operand separately. The type of the shift
expression is the promoted type of the left-hand operand.

If the promoted type of the left-hand operand is int, only the five lowest-order
bits of the right-hand operand are used as the shift distance. It is as if the right-
hand operand were subjected to a bitwise logical AND operator & with the mask
value 0x1f. The shift distance actually used is therefore always in the range 0 to
31, inclusive.

If the promoted type of the left-hand operand is long, then only the six lowest-
order bits of the right-hand operand are used as the shift distance. It is as if the
right-hand operand were subjected to a bitwise logical AND operator & with the
mask value 0x3f. The shift distance actually used is therefore always in the
range 0 to 63, inclusive.

At run time, shift operations are performed on the two's complement integer
representation of the value of the left operand.

The value of n<<s is n left-shifted s bit positions; this is equivalent (even if
overflow occurs) to multiplication by two to the power s.

The value of n>>s is n right-shifted s bit positions with sign-extension. The
resulting value is n/s. For nonnegative values of n, this is equivalent to
truncating integer division, as computed by the integer division operator /, by
two to the power s.

The value of n>>>s is n right-shifted s bit positions with zero-extension. If n is
positive, then the result is the same as that of n>>s; if n is negative, the result
is equal to that of the expression (n>>s)+(2<<~s) if the type of the left-hand
operand is int, and to the result of the expression (n>>s)+(2L<<~s) if the type
of the left-hand operand is long. The added term (2<<~s) or (2L<<~s) cancels
out the propagated sign bit. (Note that, because of the implicit masking of the
right-hand operand of a shift operator, ~s as a shift distance is equivalent to
31-s when shifting an int value and to 63-s when shifting a long value.)


kind regards,

Jos

[shana07]

I ripped this straight from the JLS Java Language Specification. Here goes:

The shift operators include left shift <<, signed right shift >>, and unsigned right
shift >>>; they are syntactically left-associative (they group left-to-right). The
left-hand operand of a shift operator is the value to be shifted; the right-hand
operand specifies the shift distance.

The type of each of the operands of a shift operator must be a type that is
convertible to a primitive integral type, or a compile-time error occurs. Binary
numeric promotion is not performed on the operands; rather, unary numeric
promotion is performed on each operand separately. The type of the shift
expression is the promoted type of the left-hand operand.

If the promoted type of the left-hand operand is int, only the five lowest-order
bits of the right-hand operand are used as the shift distance. It is as if the right-
hand operand were subjected to a bitwise logical AND operator & with the mask
value 0x1f. The shift distance actually used is therefore always in the range 0 to
31, inclusive.

If the promoted type of the left-hand operand is long, then only the six lowest-
order bits of the right-hand operand are used as the shift distance. It is as if the
right-hand operand were subjected to a bitwise logical AND operator & with the
mask value 0x3f. The shift distance actually used is therefore always in the
range 0 to 63, inclusive.

At run time, shift operations are performed on the two's complement integer
representation of the value of the left operand.

The value of n<<s is n left-shifted s bit positions; this is equivalent (even if
overflow occurs) to multiplication by two to the power s.

The value of n>>s is n right-shifted s bit positions with sign-extension. The
resulting value is n/s. For nonnegative values of n, this is equivalent to
truncating integer division, as computed by the integer division operator /, by
two to the power s.

The value of n>>>s is n right-shifted s bit positions with zero-extension. If n is
positive, then the result is the same as that of n>>s; if n is negative, the result
is equal to that of the expression (n>>s)+(2<<~s) if the type of the left-hand
operand is int, and to the result of the expression (n>>s)+(2L<<~s) if the type
of the left-hand operand is long. The added term (2<<~s) or (2L<<~s) cancels
out the propagated sign bit. (Note that, because of the implicit masking of the
right-hand operand of a shift operator, ~s as a shift distance is equivalent to
31-s when shifting an int value and to 63-s when shifting a long value.)


kind regards,

Jos

Thanks Jos...I read it..and I just still don't get it, why in order to perform gcd calculation, it involves with shift operation (binary)? i don't see the rational behind it. please share few words about it. Thanks.

[JosAH]

Thanks Jos...I read it..and I just still don't get it, why in order to perform gcd calculation, it involves with shift operation (binary)? i don't see the rational behind it. please share few words about it. Thanks.

Well, your algorithm isn't a binary gcd algorithm (it just has some slight
resemblances with it). For a full explanation read this link.

kind regards,

Jos