The trick for swapping two values without extra storage and without a dedicated swap instruction by three XORs is reasonably well known.
If you want to rotate N values, you can just do this as a sequence of swaps which under these constraints means 3(N-1) XORs.
Is there a cheaper sequence of XORs? If so, what's the asymptotic bound?
Nicolai Hähnle
npub1rh…e0uku
2025-08-13 15:16:56 UTC
Author Public Key
npub1rhnf9g9q2gcy7qval32gz9vjm543u8js0e900uzr8pftjs69yhgste0ukuSeen on
wss://relay.mostr.pubPublished at
2025-08-13 15:16:56 UTCEvent JSON
{
"id": "abb2816019041166f4706375175cde76cd28e47bdc68c7448e992b3686e90755",
"pubkey": "1de692a0a052304f019dfc54811592dd2b1e1e507e4af7f0433852b9434525d1",
"created_at": 1755098216,
"kind": 1,
"tags": [
[
"proxy",
"https://mastodon.gamedev.place/users/nh/statuses/115022116693756251",
"activitypub"
],
[
"client",
"Mostr",
"31990:6be38f8c63df7dbf84db7ec4a6e6fbbd8d19dca3b980efad18585c46f04b26f9:mostr",
"wss://relay.mostr.pub"
]
],
"content": "The trick for swapping two values without extra storage and without a dedicated swap instruction by three XORs is reasonably well known.\n\nIf you want to rotate N values, you can just do this as a sequence of swaps which under these constraints means 3(N-1) XORs. \n\nIs there a cheaper sequence of XORs? If so, what's the asymptotic bound?",
"sig": "63c613d9980c32167d03736c03cd0623debea157dbc8a67dee2e6d8a66c20b2b85d804afafdf5979669c2f24488e46993e8a72af438b90a443b7fe0ef915f400"
}