• 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
  • Paul Clapham
  • Rob Spoor
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Holloway
  • Piet Souris
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Himai Minh

Esoteric code in "Cracking the Coding Interview" Bit-Shifting, bitwise-OR-assignment operator

 
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
Called myself a "Java Developer" until I got to the first problem in this book and looked at the "efficient/optimized" solution:

1.1 Is Unique  - Write a method which determines if a given String is unique or not.

I got through the naive solution. I got through the solution in which I wasn't allowed to use any Java data-structures.
Then Ms. McDowell threw a magic voodoo curveball at me.



What in tarnation is this??
What does the `- 'a' ` doing?
who is `checker??`
and I can't even begin to wrap my head around what the "Bitwise OR assignment" does.

Can someone please break it down for me? Thank you!
 
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
       int val = str.charAt(i) - 'a';
gets the char value at index i of str, promotes it to an int, and subtracts the numeric value of 'a', which is 97, I believe, also promoted to an int.
So if the charAt(i) was 'b', val will be int value of 1.
 
Jesse Silverman
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
checker |= (1 << val);

checker is an int variable.

|= is a compound assignment, like += or *=
so the line confusing you is the same as:

checker = checker | (1 << val);

| and << are standard Java operators for bitwise integer arithmetic (or) and left shifting.
 
Jesse Silverman
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Many tutorials present bitwise integer arithmetic and shifting as esoteric, exotic, or even worse "almost deprecated".

Every application that ever needed them still does.  There are just a lot more programmers doing coding that either don't need to do them, or don't realize they need them because they don't know about them.

For decades, they were considered extremely basic, but now we are in a different world.  Except those of us that aren't.  
 
Jesse Silverman
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are some very cool things you can do with bitwise integer arithmetic.

I think my favorite is ^, exclusive or (XOR).  It has some magical properties, because X ^ X == 0 for all X...

Let's say you had an array, or even a stream of 2 million and 1 integers.

One million of them appear twice, and exactly one of them only appears a single time.

You only get to go flying thru the array once.  What is the value of the one single solitary value that is all by itself somewhere, anywhere, in that array?

Not very easy to answer unless you make a Set<Integer>, right?

Or, you can do this (it seems more impressive if you have 2 million and 1 integers, but my fingers cramped up before I could type that much):
jshell> int[] intArray = { 2, 3, 5, 7, 114, 7, 5, 3, 2};
intArray ==> int[9] { 2, 3, 5, 7, 114, 7, 5, 3, 2 }

jshell> Arrays.stream(intArray).reduce(0, (x, i) -> x ^ i)
$2 ==> 114


Bit-twiddling has gone out of style for the mainstream, but it has some real applications.
Okay, that one was faked, but looked pretty cool didn't it?
 
Jesse Silverman
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you go to study bit-shifting, there are two major differences between how Java does things and many other languages do things.

Most other languages have your choice of signed or unsigned integer quantities.

When you shift left, this makes no dang difference, because 0 bits always come in on the right.

When you shift right, what bits come in to play on the left?

Well, if they are signed and the number was negative, it stays negative by shifting 1's in.

Otherwise, 0's shift in, keeping the value positive (or zero).

Java doesn't have unsigned integral types (there are places in the API that make it easier to work with them nowadays, but you can't just declare an unsigned int like in C/C++/C# etc.)

So they use a >>> operator to indicate you want a right shift with an unsigned semantic.

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

Another thing.  In many languages if you have a 32-bit int and shift it right 33 bits, it is just gone, wiped out, to 0 or -1.

int start = 29383467;
Console.Writetln( start >> 33 ); // prints 0


Java interprets the number of bits you request shifting by modulo the size of the variable's value, so:
myInt >> 97

instead behaves exactly the same as:
myInt >> 1

You won't see that in (most) other languages, but it is part of the specification of bit-shifting in Java.

Personally, I think it makes eminent sense for rotations, where rotating more than the size of the thing you are rotating is like asking you to run around the room six times and then sit down in the chair next to the one you are sitting.

But it means identical shift expressions have different semantics, and return different results, in Java versus other languages.

I don't remember if the Java Tutorials warn you about that, but they probably should.  Lots of people work in multiple languages these days, and things that look identical and work differently can really turn your head around when they only start behaving differently once code goes into production.  What, your unit test didn't try shifting your int right by 97 places??

 
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I would reject anybody on spec who wrote a method called isUniqueChars(...).
The bit with − 'a' has an unwritten precondition, that the text comprise only lower‑case letters. You have a possible domain of letters to test, whose arity is the size of an int viz. 0x20 (=32decimal). Unless you have some documentation comments to say otherwise, that method is simply incorrect, and shows the unsuitability of bit‑shifting and bitwise (inclusive) OR for the question at hand.
 
Campbell Ritchie
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jesse Silverman wrote:. . . considered extremely basic . . .

They work very well for what they work well for.
I was supposed to be out in the middle of nowhere enjoying a bite of lunch and the sunshine, but that code put me off my dinner

. . .  things that look identical and work differently . . .

Java┬« is well‑supplied with such things; the keywords static and protected are good examples, and the behaviour of ++ operators (etc.) is another.
 
Jesse Silverman
Bartender
Posts: 1059
33
Eclipse IDE Postgres Database C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:They work very well for what they work well for.
I was supposed to be out in the middle of nowhere enjoying a bite of lunch and the sunshine, but that code put me off my dinner

. . .  things that look identical and work differently . . .

Java┬« is well‑supplied with such things; the keywords static and protected are good examples, and the behaviour of ++ operators (etc.) is another.



There are two categories.  I think the one you are referring to things that look similar to other things in Java but have different meanings, in which case I would add ClassName::instanceMethod and ClassName::staticMethod

At least I'd presume that from your ++ example.

static has a couple of ways it can be used in Java, but can't be used on local variables the way it can in C/C++ (not that it is encouraged there, but it is permitted)...

protected automatically includes access by everything in one's package, whereas in C# if you want that you say internal protected otherwise access is strictly limited to your class and its sub-classes.

Maybe you were thinking about how C/C++ lets you use ++/-- on pointers whereas Java has none and doesn't let you use them on references?  Then, okay, yeah.

I was talking about:
1 << val

Which means almost the same thing everywhere in Java, but something different than "everywhere else" i.e. for val > 32 it takes mod 32 and actually does the shift, whereas "other languages" would "shift off the end" and return 0.

These differences from other languages were likely why they used to be on OCP exams (well, SCP back then) but there is just way, way, way too much stuff in scope for those so if I am not mistaken, they were dropped as "doesn't fit in a reasonable scope".  I think the people describing them as "almost deprecated, hardly ever used" were combining the fact that they don't normally use them in their web programming with noting they were dropped from OCP scope.  Can't prove it, not sure, but that is my guess.

I agree that this only works for lowercase ASCII letters and:
123 7B {
124 7C |
125 7D }
126 7E ~
127 7F DEL
Whatever you get for other characters will be nonsense and non-portable at that, because most languages will reduce:
1 << val
to zero but Java will wind up aliasing them using module arithmetic on val

I think her books are very valuable, and contain a lot of great advice, but if you reviewed them I think you would find a good number of parts "hacky" and "full of tricks".

One famous one is "you are given only a single pointer to some specific element in a singly linked list.  There is guaranteed to be at least one element following it.  Safely delete the element pointed to from the linked list.  (You have no pointer to the head)"

There are others that I presume you'd feel the same way about, that one is the shortest to specify.

Nevertheless, if I remembered everything in those books, I'd have aced several interviews I wound up with 'nice try!" status on.

Lastly, at least the versions of the book thru the one I have does almost every example in Java, and says it is terrific to be good at other languages too, but Java is kind of non-negotiable, it is ubiquitous.  You can get away with ignoring C/C++, FORTRAN or Lisp, but not Java....so I presume she'd be fairly welcome here.
 
Space pants. Tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic