• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Java BitWise and BitShifting operators

 
Ranch Hand
Posts: 93
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

I'm learning java's bitwise [AND, OR, XOR] and bitshift [<<, >>, >>>] operators and my program is an attempt at understanding the same.
My program implements by attempting to emulate the behind the scenes working of these operators and give the desired output.

A) My research:
From the web, starting with Corey McGlone's article on bitshifting, I moved on to wikipedia's content on two's complement, one's complement,
bitwise & bitshifting operators and a few other websites relating to the same.

B) What I've understood:
bitwise operators - operate on corresponding individual bits of the bit patterns or binary values. It is a low level operation performed directly at
the processor level.
  • bitwise NOT [~]:
  • flips or inverts the individual bits of a binary value i.e 0 to 1 and 1 to 0. In other words, performs the ones complement to
    the bits of the bit pattern [8-bit byte where the 8th bit is the sign bit]. Applying the ~ operator to a decimal value, say 1,
    gives ~x = -x-1 where x == 1. So, ~1 gives -2. In binary

  • bitwise AND [&]:
  • &ing of bits returns 1 when corresponding individual bits are 1 otherwise returns 0.
  • bitwise OR [|]:
  • |ing of bits returns 0 when corresponding individual bits are 0 otherwise returns 1.
  • bitwise XOR [^]:
  • ^ing of bits returns 0 when corresponding individual bits are 0 and corresponding individual bits are 1
    [here 1 is carried to the next MSB].

    bitshift operators - shift or move the bit(s) a certain number of positions to the left or right. The bit(s) shifted out are [discarded and] replaced by the
    same number of bit(s) at the other end i.e shifted in at the other end. So, in

    Signed
  • >> operation:
  • bit(s), in a binary value, shifted out on the right are discarded. The existing bit(s) move n positions to the right [as the shifted out bit(s)]
    thereby facilitating the shifting in of bit(s) at the far left. Here, bit(s) shifted in depend on the signed magnitude or sign extension[>> operator preserves the sign]
    of the binary value. 0 is shifted in if the sign bit [aka MSB] is positive and 1 if the sign bit is negative.
  • << operation:
  • this is the reverse of the >> operation. bit(s), in a bit pattern, shifted out on the left are discarded and the same number of bit(s) are shifted
    in at the far right. Here, the sign bit is ignored and 0's are always shifted in to the far right.

    Unsigned
  • >>> operation:
  • this operates like the << operator. bit(s), in the binary value, shifted out on the right are discarded and 0's are always shifted in at the
    far left ignoring the sign bit.

    C) My program:
    As the program is humongous [excessive use of StringBuilders, arrays, for loops, nested for loops etc. within the **methods*], I've posted the pseudocode
    that I wrote down on paper before implementing the same in the program. The pseudocode is only a broad contour and not a step-by-step instructional for
    program implementation.
    If required for the sake of clarity, shall post the entire program code.

    **methods* - methods that implement program logic and those that print the results on screen, step-wise.

    [sidebar]
    The program is the culmination of researching various java concepts on the web

    and the resultant static methods written, tested, compiled and run individually before implemented in the program. Each method performs a specific, albeit
    sometimes lengthy, task and returns the result.
    [/sidebar]

    D) Program pseudocode:

    and its successful output

    For positive shift value

    For negative shift value

    To implement negative shift value, a few additional steps are inserted into the original pseudocode.


    E) My questions / doubts:
    1. Java being a higher level language, are such processor level operations useful in java programming? If yes, in which situations are they useful i.e
    when can they be used?....given that even the javadocs devotes only a single small web page to it.

    2. Why do the signed left-shift operator & unsigned right-shift operators ignore the sign bit and always shift in 0's [unlike the signed right-shift operator]?

    3. How does the signed shift operators [right and left-shift] differ from the unsigned right-shift operator?....i.e do they all operate at the bit level or does each
    operator conduct the shifting process in a different manner behind the scenes.

    Much appreciated if the responders / moderators give answers with sample code.

    Thanks,
    Sudhir
     
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .
    [list]bitwise NOT [~] . . . . . .

    I have changed it slightly to this:-
    Yes, but it is very confusing the way you have written it. You have written 9 digits where there are only 8 bits. Try it like this
    ~0b0000_0001 == 0b1111_1110
    … and it becomes a lot clearer.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    You are right about & ^ |. Remember their precedences, and that they are overloaded to operate on booleans, too.

    Sudhir Srinivasan wrote: . . . bitshift operators - shift or move the bit(s) a certain number of positions to the left or right. . . .

    Yes, it is a certain number of bits, but you need to go through the Java Language Specification (J7 edition) to find out how many. In the case of … where i and j are both integer primitives, the number of bits shifted is always j & size - 1, where size is the number of bits in i after promotion, 32 for anything other than a long. That means that only the rightmost 5 (6 for a long) bits in j are used to determine the distance to shift. Although you have shown 8‑bit numbers, the shift operations would promote them to ints. If you haven't come across i & j - 1 before, it is a bit like i % j, but j must be an integer obtainable from 2, and the result is always ≥ 0. Does that answer your question about negative shifts? They will be converted to 0 or a positive number less than the number of bits in the left operand.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .
    Signed

  • >> operation:
  • bit(s), in a binary value, shifted out on the right are discarded. The existing bit(s) move n positions to the right [as the shifted out bit(s)]
    thereby facilitating the shifting in of bit(s) at the far left. Here, bit(s) shifted in depend on the signed magnitude or sign extension[>> operator preserves the sign]
    of the binary value. 0 is shifted in if the sign bit [aka MSB] is positive and 1 if the sign bit is negative. . . .

    Forget that you have ever heard the term “sign bit” except with S&M (=Sign & magnitude) numbers. Java does not use S&M integers (but IEEE754 floating‑point numbers do actually have S&M format. Their MSB is 1=negative 0=positive). The MSB in complimentary integers determines the value. Say that the spare bits at the left are filled with the same value as the MSB, 1 or 0, not negative and positive.
    In the case of left shift there is no sign bit to ignore. Bits at the left 0 or 1 vanish in to cyber‑limbo never to be seen again and 0s are filled from the right. Soshould print true. Left‑shift by 3 places is equal to integer multiplication by 2³ and you get positive or negative values, which can change sign if you get overflow errors.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .
    E) My questions / doubts:
    1. Java being a higher level language, are such processor level operations useful in java programming? If yes, in which situations are they useful i.e
    when can they be used?....given that even the javadocs devotes only a single small web page to it.

    2. Why do the signed left-shift operator & unsigned right-shift operators ignore the sign bit and always shift in 0's [unlike the signed right-shift operator]?

    3. How does the signed shift operators [right and left-shift] differ from the unsigned right-shift operator?....i.e do they all operate at the bit level or does each
    operator conduct the shifting process in a different manner behind the scenes.

    Much appreciated if the responders / moderators give answers with sample code.

    Thanks,
    Sudhir

    That link's not javadoc, but the Java Tutorials. They are useful for masks, rapid remainders by powers of 2, particularly when you want to go from hash code to array index (never < 0, never ≥ array.length, so never throws out of bounds exceptions), cyphers, etc. As the link you posted shows, they are less useful to beginners.
    Left shift moves the MSB off the number so it is going to vanish anyway, and unsigned right shift is programmed to shift in 0s. Probably done somewhere on the chip. Don't know any more. As far as I know they are all implemented similarly, probably at the level of the chip with NOT, AND, OR, XOR and shift circuits. Don't call left shift signed; it is only right shift that is signed or unsigned. Signed right shift maintains + as + and - as -. Unsigned right shift if both operands are not 0 gives a positive result. Left shift can give + or - depending on whether you get overflow and (if you keep shifting to the left long enough), will give you 0.

    You will realise that if left shift is like repeated doubling, signed right shift is like repeated halving.
    i >> 3 equals i ÷ 2³ with the usual conventions of integer arithmetic.
     
    Sudhir Srinivasan
    Ranch Hand
    Posts: 93
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    At the outset, thank you Campbell for all your responses.

    Campbell Ritchie wrote:Try it like this
    ~0b0000_0001 == 0b1111_1110
    … and it becomes a lot clearer.


    Oh yes! Java SE 7 and later now includes binary literals as part of the existing integer literals [decimal & hexadecimal].

    The following code

    and its output

    shows the decimal equivalent - being the number system in use most of the time - of the binary values. Java SE 7 (& later) simplifies the use of binary values.
    However, I must add that learning its internal workings as shown on scjp tipline and other content on the web makes understanding the code above that much
    easier. Case in point: Looking at the code snippet that uses ~ operator to negate the bits of the binary literal, I wouldn't have a clue as to how 1
    became -2 if it were not for the behind-the-scenes insight.


     
    Sudhir Srinivasan
    Ranch Hand
    Posts: 93
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:You are right about & ^ |. Remember their precedences, and that they are overloaded to operate on booleans, too.


    How do they operate on booleans?

    Campbell Ritchie wrote:
    Yes, it is a certain number of bits, but you need to go through the Java Language Specification (J7 edition) to find out how many.


    Thanks for the link. Certainly provided the much needed clarity.
    In the case of int [size 32-bit i.e 2^5] - &ing of the right-hand operand with the bit mask 0b11111 ensures that the shift distance is always in the range 0-31 inclusive
    which conforms to the size of an int. This explains the use of only the 5 lowest order bits of the right-hand operand in any case.

    In the case of long [size 64-bit i.e 2^6] - &ing of the right-hand operand with the bit mask 0b111111 ensures that the shift distance is always in the range 0-63 inclusive
    which conforms to the size of a long. This explains the use of only the 6 lowest order bits of the right-hand operand in any case.

    As the result of the shift operation depends on the implicit casting to an int or long of the left-hand operand, the shift distance would naturally conform to either of the two
    sizes and not go beyond the respective ranges.

    Campbell Ritchie wrote:
    In the case of … where i and j are both integer primitives, the number of bits shifted is always j & size - 1, where size is the number of bits in i after promotion, 32 for anything other than a long. That means that only the rightmost 5 (6 for a long) bits in j are used to determine the distance to shift. Although you have shown 8‑bit numbers, the shift operations would promote them to ints. If you haven't come across i & j - 1 before, it is a bit like i % j, but j must be an integer obtainable from 2, and the result is always ≥ 0. Does that answer your question about negative shifts? They will be converted to 0 or a positive number less than the number of bits in the left operand.


    Yes, it certainly answers the one on negative shifts. As I've understood [as shown in my reply to your post above], the shift operations automatically promote the shift value to
    an int or long based on the type of the left-hand operand [being an int or long only] which in turn determines the outcome of the shift operation.
     
    Sudhir Srinivasan
    Ranch Hand
    Posts: 93
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:
    That link's not javadoc, but the Java Tutorials.


    Oops! You're right.

    Campbell Ritchie wrote:
    They are useful for masks, rapid remainders by powers of 2, particularly when you want to go from hash code to array index (never < 0, never ≥ array.length, so never throws out of bounds exceptions), cyphers, etc. As the link you posted shows, they are less useful to beginners.
    Left shift moves the MSB off the number so it is going to vanish anyway, and unsigned right shift is programmed to shift in 0s. Probably done somewhere on the chip. Don't know any more. As far as I know they are all implemented similarly, probably at the level of the chip with NOT, AND, OR, XOR and shift circuits. Don't call left shift signed;......


    The java tutorials seems to call << operator 'signed' while the scjp tipline and the java language
    specs conform to what you've said simply 'left-shift' operator. I guess I'll go with the latter and your post.


    Campbell Ritchie wrote:
    .....it is only right shift that is signed or unsigned. Signed right shift maintains + as + and - as -. Unsigned right shift if both operands are not 0 gives a positive result. Left shift can give + or - depending on whether you get overflow and (if you keep shifting to the left long enough), will give you 0.


    Does this mean >> operator is more ideal for signed twos complement binary numbers while the >>> operator is more useful for only positive numbers. In other words,
    for n >>> s, if n is negative, result of shift operation would still be positive as unsigned right shift is anyway programmed to shift in 0s which would cancel out the sign bit.

    Campbell Ritchie wrote:
    You will realise that if left shift is like repeated doubling, signed right shift is like repeated halving.
    i >> 3 equals i ÷ 2³ with the usual conventions of integer arithmetic.


    Got it. left shift is equivalent to left-operand * 2^n while signed right-shift is left-operand / 2^n where 'n' is the shift distance.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .
    Does this mean >> operator is more ideal for signed twos complement binary numbers while the >>> operator is more useful for only positive numbers. . . .

    It means they are intended to get different results, same sign or converted to a positive number. Depends what use you intend to make of them. If you hash a long into an int, you may prefer to have the left half of the number filled with 0s, so use >>>Remember that >>> has a higher precedence than &^|.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .
    Got it. left shift is equivalent to left-operand * 2^n while signed right-shift is left-operand / 2^n where 'n' is the shift distance.


    153 ÷ 8 =   19
    153 × 8 = 1224

    Only people get confused between ^ used to mean exponentiation and ^ meaning XOR. Look here for a bit more information about superscript numbers. I have failed to find superscript n, however.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . . How do they operate on booleans? . . .

    As logical and and logical xor and logical or and and and

    Java Language Specification (JLS) J7 again. Those bits of the JLS have been surprisingly clear, haven't they!
     
    Sudhir Srinivasan
    Ranch Hand
    Posts: 93
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:
    153 ÷ 8 =   19
    153 × 8 = 1224

    Only people get confused between ^ used to mean exponentiation and ^ meaning XOR. Look here for a bit more information about superscript numbers...


    Thanks for pointing that out . It indeed would mislead many people [except those who understand the context in which it is used and they would only be a few experts like yourself]. The link provided, again, is very useful.

    Recap:
    left-shift == left-operand * 2.
    signed right-shift == left-operand / 2.

    Campbell Ritchie wrote:...I have failed to find superscript n, however.


    This, hopefully, sets right the anomaly above.
     
    Sudhir Srinivasan
    Ranch Hand
    Posts: 93
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:

    Sudhir Srinivasan wrote: . . . How do they operate on booleans? . . .

    As logical and and logical xor and logical or and and and


    In my defense, the question arose due to my confusion between the short-circuiting AND, OR operators and the not short-circuiting AND, OR operator
    and the internal distinction of the latter [as integral types and as boolean logical types] which has been clarified by the

    Campbell Ritchie wrote:Java Language Specification (JLS) J7 again.
    Those bits of the JLS have been surprisingly clear, haven't they!


    JL specs, again, and by researching the web. The operators, & ^ | operate internally not only as integral types [which is what my
    first post focused on] but also as boolean logical operators when both operands in the shift operation are of type boolean or Boolean.
     
    Campbell Ritchie
    Marshal
    Posts: 80281
    432
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Sudhir Srinivasan wrote: . . .

    Campbell Ritchie wrote:...I have failed to find superscript n, however.


    This, hopefully, sets right the anomaly above.

    Well done finding that. It was in the same sheet of Unicode as some of the other superscripts I found, and I still managed to miss it.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic