Add portable formulas for fenwick calculations #1298
Conversation
Alongside the equations provided to calculate g(i) and h(i), I provided some alternative ones which are more portable. (Prior to C++20, it wasn't guaranteed that signed integers would be represented as two's complement, and the formulas I added do not rely on this, unlike the formulas previously mentioned in this Fenwick tree article. One exception would be when i = 0, but 0 & x, where x is any integer, is always 0.)
|
Visit the preview URL for this PR (for commit b1e3837): https://cp-algorithms--preview-1298-i1gs0veh.web.app (expires 2024-07-04T01:12:53.941446079Z) |
|
Hi there! Thanks for the pull request, but I think the article already contains some portable version? Specifically |
|
That's with a zero-based implementation, but I see your point. Personally, I feel that it should still at least be mentioned how the one-based implementation provided isn't portable (whether it's inline, as its own section, as a footnote, etc), though that's just my opinion. You can close the pr if you don't think it's necessary. |
Any computer from this century uses 2s complement, and every code judge platform does. We can mention that negation works because of 2s complement, but providing alternatives for whatever ancient microprocessor still not using 2s complement is just too pedantic. |
|
Preview the changes for PR #1298 at https://gh.cp-algorithms.com/1298/ (current version: 3d0d52e). |
Alongside the equations provided to calculate g(i) and h(i), I provided some alternative ones which are more portable.
(Prior to C++20, it wasn't guaranteed that signed integers would be represented as two's complement, and the formulas I added do not rely on this, unlike the formulas previously mentioned in this Fenwick tree article. One exception would be when i = 0, but 0 & x, where x is any integer, is always 0.)
I believe that in languages such as C, it is still not guaranteed to be two's complement, so including this in the article makes it more language/compiler-agnostic.