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
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# How to convert (n & 1) == 1 to use BigIntegers?

Ranch Hand
Posts: 57
• Number of slices to send:
Optional 'thank-you' note:
I am currently working on a project for my discrete math class and ran into an issue. I have this if statement that originally looked like this

but I need to change it to only use BigIntegers since that's what we have to use for those variables n, x, and b. I did change those variables to BigIntegers already but I need help writing the if statement.

I got this so far,

but I realize that there is redundent code on line one and that it doesn't work exactly as the top if statement. What is going wrong here? Is there a way to use Bit Wise Operators with BigIntegers?

Sheriff
Posts: 17644
300
• Number of slices to send:
Optional 'thank-you' note:
You should understand the *intent* first and then understand how those operations translate to that intent.

n & 1 is a bitwise masking operation. If n == 7, then n & 1 will result in 1. So basically, that operation says "Given a number n, if the rightmost bit of n ..."

The == 1 part means "is set"

So, the entire expression (n & 1) == 1 means "Given a number n, check if the right most bit of n is set, i.e. equal to 1"

Try it in JShell:

jshell> boolean isOneBitSet(int n) {
...>    return (n & 1) == 1;
...> }
|  created method isOneBitSet(int)

jshell> isOneBitSet(5)
\$8 ==> true

jshell> isOneBitSet(4)
\$9 ==> false

jshell> isOneBitSet(3)
\$10 ==> true

jshell> isOneBitSet(2)
\$11 ==> false

Now, if you look at that closely, then you'll see that having the ones bit set means a number is odd. Otherwise, it's even. So, what's a better way to check if a number is odd or even?

Marshal
Posts: 4468
567
• Number of slices to send:
Optional 'thank-you' note:

Steven Villarreal wrote:
Is there a case where 1 == 1 will not evaluate to true?

Junilu Lacar
Sheriff
Posts: 17644
300
• Number of slices to send:
Optional 'thank-you' note:

Steven Villarreal wrote:

but I realize that there is redundent code on line one and that it doesn't work exactly as the top if statement. What is going wrong here?

No, I wouldn't expect it to work the same way because that code says something entirely different from what the first code snippet says.

Is there a way to use Bit Wise Operators with BigIntegers?

Again, don't get caught up in the implementation. Understand the intent. I already explained what the actual intent of the first code snippet was. This is the problem with code that is too "clever" -- it hides intent behind its cleverness. IMO, it's so clever that it ends up being dumb.

Steven Villarreal
Ranch Hand
Posts: 57
• Number of slices to send:
Optional 'thank-you' note:
Good words of Advice! I will try to see what each part means first before I alter it to use BigIntegers.

Master Rancher
Posts: 4760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:
BigInteger.testBit(int) is worth a look here.

Mike Simmons
Master Rancher
Posts: 4760
71
• Number of slices to send:
Optional 'thank-you' note:
I would also note that, if for some reason we were to translate the code to BigInteger without understanding the intent, a more correct translation of

would be

That would work if needed, though it would be nicer to do as Junilu suggests and understand the intent first, to get a clearer version...

Junilu Lacar
Sheriff
Posts: 17644
300
• Number of slices to send:
Optional 'thank-you' note:

Mike Simmons wrote:BigInteger.testBit(int) is worth a look here.

Thanks, Mike for pointing that out.

Context is king; always consider context. It very well may be that this is the most appropriate translation to use if indeed the context is about checking for a bit being set rather than checking to see if the number is odd or even. And if the context was in fact about checking for a specific bit being set in n, then I'd have to retract my previous comment about being too clever.

Mike Simmons
Master Rancher
Posts: 4760
71
• Number of slices to send:
Optional 'thank-you' note:
Well, even if the goal is to identify an odd number, once you put that goal in a method name, which is better?

or

or

Maybe more people will be familiar with using the % operator on ints... but here for BigInteger, I'm not sure those techniques are any more readable than testBit().  Either way, we still need your interpretation step, to understand what (n & 1) == 1 is doing.  Whether we call it testing for oddness, or testing a bit, eh... six of one, half a dozen of the other...

Junilu Lacar
Sheriff
Posts: 17644
300
• Number of slices to send:
Optional 'thank-you' note:
I can think of at least one context where testBit might make more sense: when dealing with a digital interface, like say a micro-controller, where a bit might correspond to a specific pin being set to high or low state. It may be a stretch of the imagination but not entirely inconceivable.

Marshal
Posts: 79040
375
• Number of slices to send:
Optional 'thank-you' note:

Mike Simmons wrote:. . . the % operator on ints . .

Remembering that n % 2 == 1 doesn't reliably find odd numbers.

what (n & 1) == 1 is doing. . . .

That formula used on integer primitives will reliably identify odd numbers.

Has BigInteger got a mod() method? Yes, it has, though I confused myself by looking for BigDecimal at first. I notice that the BigInteger#mod() method doesn't have the problem you would get with n % 2 == 1

Bartender
Posts: 2236
63
• 1
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Remembering that n % 2 == 1 doesn't reliably find odd numbers.

Forget the 1. Compare to 0. You'll get n % 2 != 0 that reliably finds odd numbers.

Mike Simmons
Master Rancher
Posts: 4760
71
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Mike Simmons wrote:. . . the % operator on ints . .

Remembering that n % 2 == 1 doesn't reliably find odd numbers.

True - not that anyone had written n % 2 == 1, of course.

This does remind me why I thought testBit(0) was much more readable in the first place.

Campbell Ritchie wrote:Has BigInteger got a mod() method? Yes, it has, though I confused myself by looking for BigDecimal at first. I notice that the BigInteger#mod() method doesn't have the problem you would get with n % 2 == 1

Yes it exists, and has all along; that's why I used it.

Marshal
Posts: 8842
631
• Number of slices to send:
Optional 'thank-you' note:

Paweł Baczyński wrote:

Campbell Ritchie wrote:Remembering that n % 2 == 1 doesn't reliably find odd numbers.

Forget the 1. Compare to 0. You'll get n % 2 != 0 that reliably finds odd numbers.

So you clearly read Java Puzzlers, didn't you

Sheriff
Posts: 7125
184
• Number of slices to send:
Optional 'thank-you' note:

Paweł Baczyński wrote:

Campbell Ritchie wrote:Remembering that n % 2 == 1 doesn't reliably find odd numbers.

Forget the 1. Compare to 0. You'll get n % 2 != 0 that reliably finds odd numbers.

Help the feeble-minded out here.  Why would == 1 and != 0 be different if n is a member of the integers?

Mike Simmons
Master Rancher
Posts: 4760
71
• 1
• Number of slices to send:
Optional 'thank-you' note:
If n is negative, % can return a negative number, in this case, -1.  See examples:

Campbell Ritchie
Marshal
Posts: 79040
375
• Number of slices to send:
Optional 'thank-you' note:

Liutauras Vilda wrote:. . . you clearly read Java Puzzlers, didn't you

Didn't I introduce both you and Paweł to that book?

Liutauras Vilda
Marshal
Posts: 8842
631
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Liutauras Vilda wrote:. . . you clearly read Java Puzzlers, didn't you

Didn't I introduce both you and Paweł to that book?

I could speak for myself only, so at least about 50% of that you are right