Post Ax8jABIZppsDhItFAG by nh@mastodon.gamedev.place
 (DIR) More posts by nh@mastodon.gamedev.place
 (DIR) Post #Ax8jABIZppsDhItFAG by nh@mastodon.gamedev.place
       2025-08-13T15:16:56Z
       
       0 likes, 0 repeats
       
       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?
       
 (DIR) Post #Ax8jACRTaEaPFC3rfs by wolf480pl@mstdn.io
       2025-08-13T21:40:26Z
       
       0 likes, 0 repeats
       
       @nh pretty sure you can't do better than 6 XORs for 3 values, but there are 6^5 sequences to check so I'd have to use spin or TLA+ to prove that you can't
       
 (DIR) Post #Ax8kTBXRGfkJtgT1Ye by harold@mastodon.gamedev.place
       2025-08-13T21:55:05Z
       
       0 likes, 0 repeats
       
       @wolf480pl @nh I've done a proof-by-SAT-solver that you need 6 XORs for N=3 and 9 XORs for N=4, N=5 is looking a little hard (for this encoding+solver anyway, and I just realized that this encoding is stupid), there's no sequence of 10 XORs but 11 is still in the process of being disproven.If the answer is going to be as nice as "3(N-1) for any N" surely there's some way to prove it