{"id":111968,"date":"2026-01-06T07:00:00","date_gmt":"2026-01-06T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=111968"},"modified":"2026-01-06T06:54:48","modified_gmt":"2026-01-06T14:54:48","slug":"20260106-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20260106-00\/?p=111968","title":{"rendered":"Swapping two blocks of memory that reside inside a larger block, in constant memory, refinement"},"content":{"rendered":"

Commenter Neil Rashbrook pointed out<\/a> that my original rotation-based algorithm for swapping two blocks of memory inside a larger block did too much rotating. My solution had three rotations, but Neil was able to get it down to two.<\/p>\n

The set-up is that we have a large block of memory, and you want to swap two blocks that reside inside that large block. For concreteness, let’s say that it’s A1, A2, B1, B2, C1, C2, D1, D2, D3, E1, and you want to exchange the B’s with the D’s. Neil pointed out that you can start by rotating the BCD block to move the D’s to the front, producing ADBCE; and then rotate the BC block to move the C’s to the front, producing ADCBE.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
A1<\/td>\nA2<\/td>\nB1<\/td>\nB2<\/td>\nC1<\/td>\nC2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nE1<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u2929<\/td>\n\u00a0<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
A1<\/td>\nA2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nB1<\/td>\nB2<\/td>\nC1<\/td>\nC2<\/td>\nE1<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
\u00a0<\/td>\n\u2929<\/td>\n\u00a0<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
A1<\/td>\nA2<\/td>\nD1<\/td>\nD2<\/td>\nD3<\/td>\nC1<\/td>\nC2<\/td>\nB1<\/td>\nB2<\/td>\nE1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

There is a symmetric version where you start by swapping the B’s to the end. If you choose to swap the larger block into position first, then the number of swaps is 2n<\/var>\u00a0\u2212\u00a0max(|B|,|D|), which is a improvement over my three-rotation version that performed 2n<\/var> swaps.<\/p>\n

(But still not as good as the n<\/var> swaps that we developed later.)<\/p>\n","protected":false},"excerpt":{"rendered":"

Could do with a little less rotating.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-111968","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"

Could do with a little less rotating.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111968","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=111968"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/111968\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=111968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=111968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=111968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}