3

I'm stuying this code and I don't understand what this line does: [(y << 3) + x]

    for (int y = 0; y <= 7; ++y) {
            for (int x = 0; x <= 7; ++x) {
                final String pieceCode = pieceCodes[(y << 3) + x];
                if (pieceCode.length() != 2) throw new IllegalArgumentException();
                if (!pieceCode.equals("--")) {
                    pieces[((7 - y) << 3) + x] = CheckersPiece.valueOf(pieceCode.charAt(0), pieceCode.charAt(1));   
                }
            }
        }
kosa
  • 65,990
  • 13
  • 130
  • 167
user2520410
  • 459
  • 1
  • 5
  • 12

9 Answers9

6

It's an obfuscated way of multiplying by 8. Thus, (y << 3) + x is equal to 8 * y + x.

The reason that y << 3 is equivalent to multiplying by 8 is because << is the left-shift operator: it shifts all the bits of y left by one position. In the same way that if you take a base-10 number and shift left by one position you have multiplication by 10, shifting left in base-2 is equivalent to multiplying by 2. Therefore, shifting left by three positions is equivalent to multiplying by 2 * 2 * 2 = 8. In general, shifting left by n positions is equivalent to multiplying by 2^n (as long as you don't have bits falling off of the left end).

In the olden days, programmers wrote code like this because left shifts are super duper fast, faster than multiplication and so 8 * y was less optimal than y << 3. But these days, compilers are pretty good at figuring out when to replace something like 8 * y with y << 3.

Therefore, I say it's obfuscated because 8 * y more clearly expresses the intent: the intent of (y << 3) + x is to skip by y blocks of 8, and take the xth position in that block. And this is much more clearly expressed by saying 8 * y + x. Remember, we code in high-level languages for humans to read and understand the code. Our code should be written for the humans. The compiler can do its job of making good machine instructions for the machine to understand.

It's done this way because it's trying to pretend that pieceCodes is a 2D array, just mapped into a 1D array.

That is, piecesCode looks like this

x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x

but we can pretend it looks like this

x x x x x x x x 
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x

See, given (x, y) -> 8y + x we accessing the xth column, yth row of piecesCode. That is, y tells us how many blocks of 8 to skip, and x tells us where to go within that block.

jason
  • 236,483
  • 35
  • 423
  • 525
  • 3
    It's not necessarily obfuscated. – Marko Topolnik Jul 25 '13 at 15:29
  • 4
    I'm old enough it's not obfuscated :( – Dave Newton Jul 25 '13 at 15:29
  • 1
    specifically, `(y << n) + x` is equivalent to `(y * (2^n)) + x` – Russell Uhl Jul 25 '13 at 15:30
  • I think you confused "obfuscated" and "canonical". – Ingo Jul 25 '13 at 15:39
  • I think in a language like java with a pretty smart runtime optimizer, it's fair to call this obfuscated. If the "pretend" array been 5 elements instead of 8, the coder would have had to multiply or shift *and* add which would be even uglier. – Ian McLaird Jul 25 '13 at 15:45
  • 3
    I say it's not obfuscated because every software engineer should be as comfortable with the binary system as with the decimal system. For example, it will be more natural to resize the array in question by changing `y << 3` to `y << 4` than by changing `8*y` to `16*y`. That's because 8 and 16 are a quite awkward way of writing down two **round** numbers. – Marko Topolnik Jul 25 '13 at 15:46
  • Yes, @IanMcLaird, but some things never change, like the size of a chess board. And obfuscated it is only for the young folk that deem well known clichees of the elder days "unreadable". Hence, canonical. – Ingo Jul 25 '13 at 15:48
  • 1
    Is there anyone that wouldn't understand that `8 * y` means multiply `y` by 8? Are there people that don't understand that `y << 3` means multiply `y` by 8? Yes, obviously. Additionally, `y << 3` doesn't express what's really going on here but `8 * y` does. It does because it says "skip by 8" whereas `y << 3` says "shift left by 3". It's the former that we want to be saying, and we don't need to use a *less* clear mechanism to express that. – jason Jul 25 '13 at 16:03
  • 1
    Guys, it's obfuscated whether or not *every* programmer *should* understand this because it doesn't clearly express the intent. I do *not* disagree *every* programmer should know this. But just because some programmers are use to seeing it this way doesn't mean that there aren't clearer ways to express exactly the same thing. It's obfuscated because it's less clear than the alternatives. – jason Jul 25 '13 at 16:06
  • 1
    Who is judging, Jason? You? And how do you know "it's less clear". To me, at least, it is **more** clear, as I see, aha, address arithmetic going on, as opposed to some arbitrary numeric calculation. – Ingo Jul 25 '13 at 16:08
  • Arbitrary numeric calculation? This is *obviously* row-major addressing, get real. And what would you be doing were this array 17 by 17 and not 8 by 8. We're lucky here it's a power of two. `17 * y + x` is going to be a lot more clear than `(y << 4) + y + x`. Come on. – jason Jul 25 '13 at 16:10
  • 1
    @Jason Just as another data point, I also find this notation clearer than (8 * y) + x, but that's partially because I'm old. – Dave Newton Jul 25 '13 at 16:13
  • 1
    @Ingo: You just *can not* rationally argue that `y << 3` is a *more* clear way of multiplying by 8 than `8 * y`. *Should* every programmer know that they are the same? Yes. But that still doesn't change the fact that the crystal clearest way to multiply by 8 is to say `8 * y`, not `y << 3`. – jason Jul 25 '13 at 16:13
  • 1
    But you can't necessarily argue the converse either. And besides, just because one variant may be clearer (in the eyes of some) doesn't necessarily mean that the other is "obfuscated". – arshajii Jul 25 '13 at 16:18
  • @Jason I am arguing that I recognize the pattern `(a << k) + b` better than `(a * n) + b`, the latter one being nothing special. Of course, if it's 17, then I'd not write it as `(a << 4) + a + b`. I am also opposing, on principle, the psychologism in our profession - as if "readable" could ever be anything but a **subjective judgement**. Often used to rationalize a **race to the bottom** (aka, we can only use that parts of a programming language the weakest prospective team member could understand.) – Ingo Jul 25 '13 at 16:25
  • Is `1e3` an obfuscated way to write `1000`? The argument is exactly the same. – Marko Topolnik Jul 25 '13 at 16:31
  • @Ingo, in principle, I agree with you, but really bitshift operations are for bit-pattern manipulation, not math (yeah, I know it reduces to the same thing -- intent matters). Had this been a 19 x 19 Go board (since you brought up chess), then we'd be looking at `(y << 4) + (y << 1) + y + x` instead of `19 * y + x`. Of course, either of these issues could be cleared up by a nice comment on the "funny-looking" code, perhaps even explaining the choice to use a one-dimensional array as though it were two-dimensional. – Ian McLaird Jul 25 '13 at 16:42
  • 1
    @IanMcLaird 1D-arrays are more memory efficient and it is quite plausible that a "computer player" must instantiate a heavy lot of board positions in order to find the best move. – Marko Topolnik Jul 25 '13 at 16:45
  • 2
    @Ian, I am with you regarding the Go board. – Ingo Jul 25 '13 at 16:45
  • @MarkoTopolnik, and that is precisely the sort of comment I was saying should be in the code ;). I didn't say it was a bad choice, I was saying it's a choice that should have an explanation. The next person to maintain your code could be a new graduate without a lot of engineering experience. Help the poor kid get better by explaining your design. – Ian McLaird Jul 25 '13 at 16:51
  • @IanMcLaird Ah, if the kid can't see *that* on his own, there's just no amount of comment that's going to save the project from his inept hands. But I've realized that using a full array is wasteful in itself: the whole board position fits into just two `long`s! :) – Marko Topolnik Jul 25 '13 at 19:48
3

(y << 3) means bit shifting 3 times to the left. It's the same as multiplying by 2^3 = 8. So, whole expression (y << 3) + x becomes y * 8 + x.

It should be written in the form y * 8 + x, because it's more readable and very probably there is no performance gain. Premature optimization is the root of all evil. It's better to left such micro optimizations to the compiler (or JVM).

Moreover, board size could be stored in a constant, to have it only in one place:

final int SIZE = 8;
// ...
for (int y = 0; y < SIZE; y++) {
    for (int x = 0; x < SIZE; x++) {
        final String pieceCode = pieceCodes[y * SIZE + x];

y * 8 + x is just iterating over a (logically) 2D table with 8 rows and columns, stored as 1D, with 64 cells.

As a final remark, I would like to point out, that in the given code pieceCodes is an array of Strings... But in fact, it's an array of piece codes. Not just some Strings. Now, "--" works as some magic state and nobody except the programmer knows, what it means. if (pieceCode.length() != 2) also looks bad. So, there should be an object PieceCode and array will be declared as PieceCode[] pieceCodes. In PieceCode we can implement proper equals() method. If PieceCode is only a state, it can be an Enum. For example EMPTY, WHITE_PAWN, WHITE_QUEEN, BLACK_PAWN, BLACK_QUEEN. Comparing Strings is not as fast as comparing Enums. We also have to watch out to write equals(), instead of ==.

Adam Stelmaszczyk
  • 19,665
  • 4
  • 70
  • 110
2

From the spec:

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.

user1111284
  • 886
  • 1
  • 6
  • 23
2

<< and >> are bit shift operators. In this case, it converts y to binary and "shifts" over 3 places, adding new bits to the end as required

For example, if y was 8, it would have the value of 1000

y<<3 would shift to the left 3 bits, resulting in 1000000, or 64

Song Gao
  • 666
  • 4
  • 14
2

The code uses an optimization technique that represents a two dimensional array[m][n] as a one dimensional array[m*n]. Both m and n appear to be 8 here (8-queens, chess, maybe?).

The trick is to transpose index tuples (i,j) to indexes for the one dimensional array.

Most of the time, you do this by multiplying i with n and add j.

Since n=8, multiplication can be expressed in this case by shifting 3 bits left. This conveys the message "We are doing adress arithmetic here on some nicely sized (i.e. in terms of power of 2) arrays.", at least to the non-novices.

Ingo
  • 36,037
  • 5
  • 53
  • 100
  • 2
    I would guess checkers because `CheckersPiece`. Just a hunch. – Dave Newton Jul 25 '13 at 15:34
  • 1
    I don't see why everyone assumes shifiting is motivated by optimization. In my code I use it for clarity: to emphasize the binary roundness of the numbers in question. `1<<31`, for example is way simpler, more readable, and more obvious than `2147483638`. – Marko Topolnik Jul 25 '13 at 15:53
2

That is called a bitwise and bit shift operator. Also, check out the wiki.

Summary of the documentation

The Java programming language also provides operators that perform bitwise and bit shift operations on integral types. The operators discussed in this section are less commonly used.

The unary bitwise complement operator "~" inverts a bit pattern. The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right.

The bitwise & operator performs a bitwise AND operation.

The bitwise ^ operator performs a bitwise exclusive OR operation.

The bitwise | operator performs a bitwise inclusive OR operation.

Example code:

class BitDemo {
    public static void main(String[] args) {
        int bitmask = 0x000F;
        int val = 0x2222;
        // prints "2"
        System.out.println(val & bitmask);
    }
}

So... What is a bitwise and bit shift operator?

In order to save time and space, I'll simply include this article explaining all operators in depth!

Scientious
  • 337
  • 1
  • 8
1

Quick answer, it's an efficient way of multiplying a number by 8 (2^3=8)

tehawtness
  • 266
  • 4
  • 15
  • 1
    Why it is efficient ? – AllTooSir Jul 25 '13 at 15:30
  • I really doubt that the shifting is in any way faster than the multiplication by 8. Also, it's way less readable. – f1sh Jul 25 '13 at 15:34
  • It's unlikely to be significantly more efficient, any more. Back in the day the shift-by-two opcode was faster than than the general multiple opcode, i.e., it was faster to multiply by a power of two by shifting and add than to use multiply. – Dave Newton Jul 25 '13 at 15:36
  • 1
    @DaveNewton Generally, register shifts are much faster than multiplication. However, also (JIT) compiler writers know this and will replace 8*n by the fastest opcode sequence. Maybe something like `load a, n; add a,a; add a,a; add a,a` is even faster. That being said, for us elder ones the notation `(a << n) + b` is very familiar and readable and it tells us that it is most probably an indexing operation going on (rather than some "numeric" computation). It doesn't hurt the greenhorns if they learn this, too. – Ingo Jul 25 '13 at 15:45
  • If its not more efficient in c I don't how it would be in Java unless you are using a old CPU http://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster – Michael M Jul 25 '13 at 15:45
  • Maybe it's time for grandpa to learn that the compiler takes care of this. The reason we got into programming is to automate away stuff. Should we also learn assembly just because? No offence mate. I would rather write code that is understandable. Another programmer is after all still a "user" at least of my code, and I see more merit in writing user friendly code. – Michael M Jul 25 '13 at 15:53
  • @Ingo Depends *entirely* on the processor; look at an assortment of modern processor instruction timings and you'll find this is *often* no longer the case at all, and even when it *is* faster might be barely 1-2% improvement. It's incredibly dependent on architecture. – Dave Newton Jul 25 '13 at 16:00
  • 1
    @Michael.M My whole point is that it *is* readable, and very much so. You can't say it's not readable only because there are some dozens of millions of adepts in countries like India, etc. who do not understand it. Why should we adapt **downwards**? Can't they learn it? It's not rocket sience, yet if you follow SO closely you find that many "developers" have not the slightest clue about OS, machine architecture, basic handling of a command line, etc. Once their IDE stops working, they're just out of luck. It does not have to be so. – Ingo Jul 25 '13 at 16:05
  • 1
    @Ingo Hate to disappoint you, but there are a lot of non-Indians who are equally clueless--this isn't about country of origin. – Dave Newton Jul 25 '13 at 16:11
  • @DaveNewton I am only disappointed because you misinterpret me. I said "countries like India" qualified by "there are millions of adepts." - I know firsthand that there are very very knowledgeable Indians, as well as extremely dumbfolded . – Ingo Jul 25 '13 at 16:14
  • @Ingo Apologies for the misinterpretation--IMO it's just best to leave out *any* possibility of racism; I think it's clear that the sentence is easy to read wrong. – Dave Newton Jul 25 '13 at 16:19
  • Yes, please replace *countries like India* with *all over the world*. – Ingo Jul 25 '13 at 16:29
  • Pages like this exist for people who don't understand "<<"; and for everyone of these pages, how many pages are there for people that need to make (2^3=8) faster because their compiler can't do it? In other words using "<<" creates problems while generally solving none. – Michael M Jul 25 '13 at 19:31
1

y << 3 means "shifted 3 bits left" ... which is, essentially, another way to do "* 8"

If you do a right-shift (y >> 3), that would be integer divide by eight, but is also useful because the bits fall off the end, and you sort of "drain" the bits if you loop.

It used to be (way way back when) that CPU shift was faster than multiplication, so using "x << 1" was faster than "x * 2". However, that's not true anymore.

I used to see expressions in code like "x << 4 + x << 2 + x << 1" ... which is really "x * 16 + x * 4 + x * 2" or "x * 22".

sea-rob
  • 2,275
  • 1
  • 22
  • 22
1

http://en.wikipedia.org/wiki/Bitwise_operation ... In Java, all integer types are signed, and the "<<" and ">>" operators perform arithmetic shifts. Java adds the operator ">>>" to perform logical right shifts, but because the logical and arithmetic left-shift operations are identical, there is no "<<<" operator in Java.

Michael M
  • 8,185
  • 2
  • 35
  • 51