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

51–60 of 73 posts

Re: Inverting a binary tree using x64 assembly

#51

Post by quelsolaar »

rags2riches wrote: post #45
quelsolaar wrote: post #41

Earlier quoted context omitted.

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.

Yes, you are right!

Re: Inverting a binary tree using x64 assembly

#52

Post by mananaysiempre »

rags2riches wrote: post #45
quelsolaar wrote: post #41

Earlier quoted context omitted.

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.

Indic scripts are LTR, and so stayed the big-endian numerals when they were borrowed by medieval Islamic mathematicians. Numerals in modern spoken Arabic are big endian (mostly, with an exception for the teens that also exists in English).

Re: Inverting a binary tree using x64 assembly

#53

Post by saagarjha »

kristov wrote: post #49
tom_ wrote: post #44

Earlier quoted context omitted.

"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?

Sure, it’s the binary tree equivalent of reversing an array.

Re: Inverting a binary tree using x64 assembly

#54

Post by sedatk »

dekhn wrote: post #46
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).

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

No, but that's how I peel an egg.

Re: Inverting a binary tree using x64 assembly

#56

Post by userbinator »

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).

Try to find (or even better, write) a big-endian arbitrary-precision arithmetic implementation if you're convinced that the difference is frivolous. You'll easily see why one is sometimes called "logical endian" and the other "backwards endian".

Re: Inverting a binary tree using x64 assembly

#57

Post by roperj »

adrian_b wrote: post #28
danbruc wrote: post #15

Assume RAX points to the root node and nodes just contain two child pointers and everything is aligned and whatever. :invert cmp rax, 0 jnz swap: ret :swap push rax mov rax, [rax] call invert mov rbx,[rsp] xchg rax, [rbx+8] mov [rbx], rax call invert pop rax ret The last time I used an assembler was before x86-64 was invented, I am not even sure I ever used one in protected mode. But that seems a totally reasonable w…

The variables on the stack are the most efficient after registers, so you are right that a local variable should be kept into a register if possible, otherwise in the stack, and only then in other places (e.g. if it is too large for the stack). However, when writing in assembly one must pay attention that at least RBX, RBP and R12 through R15 must be preserved by any function (on Windows also RDI and RSI must be pres…

> The variables on the stack are the most efficient after registers

Why are variables on the stack more efficient than other memory accesses?

Re: Inverting a binary tree using x64 assembly

#58

Post by userbinator »

adrian_b wrote: post #28
danbruc wrote: post #15

Assume RAX points to the root node and nodes just contain two child pointers and everything is aligned and whatever. :invert cmp rax, 0 jnz swap: ret :swap push rax mov rax, [rax] call invert mov rbx,[rsp] xchg rax, [rbx+8] mov [rbx], rax call invert pop rax ret The last time I used an assembler was before x86-64 was invented, I am not even sure I ever used one in protected mode. But that seems a totally reasonable w…

The variables on the stack are the most efficient after registers, so you are right that a local variable should be kept into a register if possible, otherwise in the stack, and only then in other places (e.g. if it is too large for the stack). However, when writing in assembly one must pay attention that at least RBX, RBP and R12 through R15 must be preserved by any function (on Windows also RDI and RSI must be pres…

However, when writing in assembly one must pay attention that at least RBX, RBP and R12 through R15 must be preserved by any function

Only if you're calling external code that assumes that. The power of Asm largely comes from not needing to follow arbitrary conventions in your own code. The boundaries where you interface to external code are the only constraints.

Re: Inverting a binary tree using x64 assembly

#59

Post by comex »

userbinator wrote: post #56
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).

Try to find (or even better, write) a big-endian arbitrary-precision arithmetic implementation if you're convinced that the difference is frivolous. You'll easily see why one is sometimes called "logical endian" and the other "backwards endian".

Or try to read numbers in a hex editor, and quickly obtain the opposite conclusion. :)

Re: Inverting a binary tree using x64 assembly

#60

Post by nmilo »

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).

Genuinely curious, what are any advantages of big endian other than "it's how we write numbers in base 10?"
Post reply on HN