• 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
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Interesting way to check for odds and evens

 
Ranch Hand
Posts: 217
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Normally, I've only see implementations which utilize the modulo operator, but this I like this one and it works perfectly well.... except I can't figure out HOW it's working:



What exactly is happening here? The way I'm reading it, it looks like the condition is saying: "If number and 1 are true." That makes absolutely no sense. Some please shed some light on this.


 
Ranch Hand
Posts: 91
Netbeans IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Hi,

It makes sense if you think binary
 
Saloon Keeper
Posts: 8596
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Binary:
 
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can get that sort of thing to work if the right operand of the & operator is 1, 3, 7, 0xf, 0x1f, 0x3f, etc. Obviously those test for zero remainders when you divide by different numbers.
 
Master Rancher
Posts: 4465
38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

test for zero remainders when you divide by different numbers.


Can you explain what you mean there?  The bitwise operator: &  does not  divide.
 
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
x % 2 == x & 1
x % 4 == x & 3
et cetera.

As Campbell writes, it boils down to dividing and determining the remainder.

@OP
I think it is now obvious from all the preceeding posts, but since 4 = 2 x 2, can you devise a similar way to determine whether a number is divisable by 4? And by 8?

Similar: a multiplication might take several clock ticks from the processor. Assuming a bit shift can be done in one clock tick, can you devise a fast way to multiply by 2 without using a multiplication? And by 4? And by 5?
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:x % 2 == x & 1
x % 4 == x & 3
et cetera.. . .

Not quite. As long as the right operand for & is a positive number, that expression cannot produce a negative result. The remainder operator % often does produce a negative result.
 
Carey Brown
Saloon Keeper
Posts: 8596
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Not quite. As long as the right operand for & is a positive number, that expression cannot produce a negative result. The remainder operator % often does produce a negative result.

Do we care if it produces a negative result, as long as when it's evenly divisible it returns zero? Even if we are trying to find the actual remainder it should still work for other purposes. -4 % 3 == -1
 
M Richardson
Ranch Hand
Posts: 217
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:x % 2 == x & 1
x % 4 == x & 3
et cetera.



Okay, so I know that  x % 2 in plain English means "Give us  x divided by 2's remainder."

So, 10 % 4 would be 2, as the remainder.

Now, I've used the & operator in Java to make sure that two conditions are true within an if statement. That's about the only place where I've seen any textbook mention it too.



In plain English, what exactly is this doing? I know it's giving back a 1 if the number is odd, and a zero if the number is even.. but how?



 
Carey Brown
Saloon Keeper
Posts: 8596
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"&&" is "logical AND"
"&" is "bitwise AND"

Truth table for "&"
If you "&" two ints together it performs this bitwise AND for each pair of bits.

So, if you have two ints, one is 12 (radix 10) then it is the binary bits "1100"
and you have a second int 1 (radix 10) then it is the binary bits "0001"

To AND the bits together you get
The result is zero, meaning that the least significant bit was not set. The least significant bit represents the ones place in a binary number. If this bit is one then it is an odd number else it is an even number.

An example of ANDing an odd number: 13, which in binary is "1101".
Result is non-zero, meaning "odd".

That's the best I can do on short notice. The study of binary arithmetic would take at least a chapter if not more.
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Not quite. As long as the right operand for & is a positive number, that expression cannot produce a negative result. The remainder operator % often does produce a negative result.


Indeed! I just had a look at the JLS 8, section 15.17.3, that states this in a clear way.

Gosh, I was raised with that fundamental theorem that there is one and only one way for integers a and b such that a = k * b + c, with 0 <= c < b, so that the 'remainder' was always non-negative....

@Mark
today bit manipulation is hardly ever necessary, but in the 90's I had a computer that defined many characteristics of a frame or icon (including things like textfields) with the help of several 32-bit integers, where each bit had a certain meaning, like if the icon contained text, what sprtie was being used, whether a window was resizable, et cetera.
If you ever wanted to change that state, you had to call a certain OS-routine with three parameters: the window or icon in question, a 'clear' word and an 'Exclusive OR' word, and this formula was applied:
new state = (old state and NOT 'clear word') Exclusive or 'EOR word'.

With this formula, you get the following table:

Value of CE       Effect
00                preserve the bit's status
01                toggle the bit's state
10                clear the bit
11                set the bit


Now, this is not very intuitive (but in those days you did not know any better), so I wrote a program with three textfields, one where you could mention all the bit numers to be cleared, one for the bits to be set, one for the bits to be toggled (the unmentioned bits were not changed).

Now, it is a nice exercise to have a routine, that, given two integers a and b, determines the Clear and the EOR words necessary to change a into b. Well, something for a rainy wednesday afternoon!
 
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nice discussion. It made me curious if there were other ways and I found this http://www.speakingcs.com/2015/06/4-ways-to-check-given-integer-is-even.html

My advice to you, Mark, is to prefer clarity over cleverness. Most programmers will know what your intent is if they see x % 2 == 0 because that is the most common and straightforward way. In the real world, you should go with what most people can readily recognize as correct. If you have a good reason to do something different, be sure to explain why in a comment.

Finally, prefer to keep it high-level and abstract:

Hide the details of the implementation behind a name that reveals your intent clearly. This is what makes you a better programmer, in my opinion, not so much how cleverly you can write the implementation.
 
Saloon Keeper
Posts: 24330
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:
today bit manipulation is hardly ever necessary, but in the 90's I had a computer that defined many characteristics of a frame or icon (including things like textfields) with the help of several 32-bit integers, where each bit had a certain meaning, like if the icon contained text, what sprtie was being used, whether a window was resizable, et cetera.



The technical term for this is "bit field", and it's an integral part of some programming languages, including C:



By defining items as bit-addressible, you could set and test them without any special operators or function calls.

Bit fields were rampant on the old mainframes, where RAM was measure in KiloBytes. They're not usually used in high-level languages of today as they generally sacrifice CPU efficiency for storage efficiency. Related constructs are things like this:


Note that the proper pronunciation of "x % y" is X MODULO Y. The modulus operator is actually named "mod" in some languages. It's a percent in the terser languages simply because the diagonal stroke in the percent symbol suggest the use of a similar stroke for the division operator's symbol. Nothing to do with actual percentages.

Incidentally, many compilers look at division and modulo operations and look for common and easily-optimized values, such as 2, 4, 5, 10, and the like and reduce them to bit operations or bit-shift functions. Division, whether for modulus or quotient (or both) is relatively expensive.

Some languages also have a divmod function so that they can obtain both parts from a single operation, but here again, optimizing compilers can often do the same job automatically.
 
author
Posts: 23907
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Agreed. I also think that the OP is confusing the logical AND operator with the bitwise AND operator. Once the OP realizes that these are two different operators, that does different operations, and understand what the bitwise AND operator does, then it should become clear.

Henry
 
M Richardson
Ranch Hand
Posts: 217
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Henry Wong wrote:
Agreed. I also think that the OP is confusing the logical AND operator with the bitwise AND operator. Once the OP realizes that these are two different operators, that does different operations, and understand what the bitwise AND operator does, then it should become clear.

Henry



Hmm I see now. I went to the operator precedence table, and I see that "& ^  |" are all Bitwise operators (as well as being logical operators) As for what they exactly do in the bitwise context is kind of beyond me, but I would imagine that until I go and get a primer on how binary works, it wont make much sense, am I right?
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mark Richardson wrote:As for what they exactly do in the bitwise context is kind of beyond me, but I would imagine that until I go and get a primer on how binary works, it wont make much sense, am I right?


You're right.

See https://en.wikipedia.org/wiki/Bitwise_operation and https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
the only case I make use of bit operations nowadays is when I deal with colors. If you have a color (say a 32 bit ARGB color), then each of the color parts alpha, red, green and blue take up 8 bits. So you can get:
where each of the parts is an 8 bit byte (so with a value between 0 and 255).

But it doesn't get more complex than that. Even if this is already too complex, there is a constructor that takes these four parameters.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . there is a constructor that takes these four parameters.

It probably looks like this Actually there is some testing to ensure that the four arguments are in the range 0...0xff before any bitwise operations are used.
 
Piet Souris
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Probably, yes. Mind you, in this constructor the a (alpha component) is the fourth parameter, so you have new Color(r, g, b, a).
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic