Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Inverting a binary tree using x64 assembly

sanket.tech

Post reply on HN
Print view View original

41–50 of 73 posts

Re: Inverting a binary tree using x64 assembly

#41

Post by quelsolaar »

sedatk wrote: post #22
_8j50 wrote: post #11

Earlier quoted context omitted.

AT&T really is annoying but it feels like the big vs little endian debate. Fairly easy to convert between the two as well.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

I used to be big endian. Then i changed my mind. Have a look at the following:

-123 -12 -1

Here are three numbers. If we read them from left to right, they all begin with 1, but we cant tell what the 1 means, in one case it means 100, in one it means 10 and in one it means 1. We need to parse the entire number to know what the first number means. If we parse from right to left, each number always means the same thing. the first is how many once, the second how many 10s and so on.

So it makes sense to store the smallest first. In a big endian architecture, if i want to read an 8, 16, 32 or 64 bit word each byte will always mean the same, if we pad out the type with zeros. So little endian is right, and Arabic numerals are wrong.

Re: Inverting a binary tree using x64 assembly

#43

Post by Kranar »

devit wrote: post #27

That solution is terrible, with a bad algorithm that requires O(tree_height) space (the optimal one involves temporarily using left/right pointers as a parent pointer so that you only need constant space) and lacking any sort of assembly optimization, being worse than what a compiler would produce (e.g. it's a real mystery how the author managed to decide that local_right should be spilled on the stack). Definitely n…

You're alluding to using the Morris traversal algorithm which can traverse a binary tree in O(1) space, but Morris traversal is actually much much slower than using a stack, especially as is used by this algorithm. Doing a Morris traversal requires at a minimum twice the number of operations as using a stack, and due to its cache unfriendly nature will in practice be closer to 4x slower.

You typically only use Morris traversal on exceptionally large trees, and by large I mean when working with data that lives on a disk. It's definitely the exception, not the norm.

Re: Inverting a binary tree using x64 assembly

#45

Post by rags2riches »

quelsolaar wrote: post #41
sedatk wrote: post #22

Earlier quoted context omitted.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

I used to be big endian. Then i changed my mind. Have a look at the following: -123 -12 -1 Here are three numbers. If we read them from left to right, they all begin with 1, but we cant tell what the 1 means, in one case it means 100, in one it means 10 and in one it means 1. We need to parse the entire number to know what the first number means. If we parse from right to left, each number always means the same thing…

Arabic numerals are little endian when writing right-to-left. Like Arabic is written.

Re: Inverting a binary tree using x64 assembly

#46

Post by dekhn »

sedatk wrote: post #22
_8j50 wrote: post #11

Earlier quoted context omitted.

AT&T really is annoying but it feels like the big vs little endian debate. Fairly easy to convert between the two as well.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

Wait, hasn't everybody learned about inside-out endian? The highest order bit is in the middle, then proceeds along a hilbert path to the edges

Re: Inverting a binary tree using x64 assembly

#47

Post by quietbritishjim »

quelsolaar wrote: post #41
sedatk wrote: post #22

Earlier quoted context omitted.

For those who don't know, that's why big and little endian were called that, because the debate was so frivolous. It's a reference to the book Gulliver's Travels by Jonathan Swift in which an island folk was split about from which end you should crack a boiled egg. (I'm a big endian for example).

I used to be big endian. Then i changed my mind. Have a look at the following: -123 -12 -1 Here are three numbers. If we read them from left to right, they all begin with 1, but we cant tell what the 1 means, in one case it means 100, in one it means 10 and in one it means 1. We need to parse the entire number to know what the first number means. If we parse from right to left, each number always means the same thing…

It looks like the comment you're replying to was talking about eggs. I'm little endian by the way.

Re: Inverting a binary tree using x64 assembly

#48

Post by dekhn »

aftbit wrote: post #42

What does it mean to "invert" a binary tree?

Inverting a binary tree is easy; express the tree as a matrix (laplacian), invert the matrix, then convert that back to a tree. What the canonical question is asking is not inversion.

Since too many people were memorizing inversion, I switched to asking how to evert a binary tree. This leads naturally into a discussion of the 1:1 relationship between complex numbers and cohomology sets, I figure if somebody can get that right, they can be a junior programmer on the team.

Re: Inverting a binary tree using x64 assembly

#49

Post by kristov »

tom_ wrote: post #44
aftbit wrote: post #42

What does it mean to "invert" a binary tree?

"Flip" or "mirror" is probably a better term. It seems the goal is to swap left and right: https://leetcode.com/problems/invert-binary-tree/

Is there a practical reason to do this in a real-world program?

Re: Inverting a binary tree using x64 assembly

#50

Post by nixpulvis »

Someone wrote: post #35
scheme271 wrote: post #30

Earlier quoted context omitted.

The xor reg, reg is also special cased because it's a quick way for compilers to reinitialize a register and indicate that future uses of that register don't depend on any previous operations. It helps the cpu to parallelize any future instructions that use that register since the cpu knows that those instructions don't depend on anything that happens before the the xor.

It’s not special cased because it's a quick way for compilers to reinitialize a register and indicate that future uses of that register don't depend on any previous operations, it’s special cased to give compilers a quick way to reinitialize a register and indicate that future uses of that register don't depend on any previous operations. https://randomascii.wordpress.com/2012/12/29/the-surprising-... is almost ten y…

Exactly! I was almost expecting to find a special instruction for this, but then again, why waste the opcodes!?
Post reply on HN