{"id":25773,"date":"2017-10-25T20:26:51","date_gmt":"2017-10-25T14:56:51","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25773"},"modified":"2017-10-25T20:26:51","modified_gmt":"2017-10-25T14:56:51","slug":"swap-bits-given-number","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/swap-bits-given-number\/","title":{"rendered":"Swap bits in a given number"},"content":{"rendered":"

Given a number x and two positions (from right side) in binary representation of x, write a function that swaps n bits at given two positions and returns the result. It is also given that the two sets of bits do not overlap.<\/p>\n

We strongly recommend that you click here and practice it, before moving on to the solution.<\/strong><\/p>\n

Examples<\/strong>:<\/p>\n

Let p1 and p2 be the two given positions.\r\n\r\nExample 1\r\nInput:\r\nx = 47 (00101111)\r\np1 = 1 (Start from second bit from right side)\r\np2 = 5 (Start from 6th bit from right side)\r\nn = 3 (No of bits to be swapped)\r\nOutput:\r\n227 (11100011)\r\nThe 3 bits starting from the second bit (from right side) are \r\nswapped with 3 bits starting from 6th position (from right side) \r\n\r\n\r\nExample 2\r\nInput:\r\nx = 28 (11100)\r\np1 = 0 (Start from first bit from right side)\r\np2 = 3 (Start from 4th bit from right side)\r\nn = 2 (No of bits to be swapped)\r\nOutput:\r\n7 (00111)\r\nThe 2 bits starting from 0th postion (from right side) are\r\nswapped with 2 bits starting from 4th position (from right side) \r\n\r\n<\/pre>\n
Solution<\/strong>
\nWe need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers. Following is the algorithm.<\/p>\n
1) Move all bits of first set to rightmost side\r\n   set1 =  (x >> p1) & ((1U << n) - 1)\r\nHere the expression (1U << n) - 1<\/em> gives a number that \r\ncontains last n bits set and other bits as 0. We do & \r\nwith this expression so that bits other than the last \r\nn bits become 0.\r\n2) Move all bits of second set to rightmost side\r\n   set2 =  (x >> p2) & ((1U << n) - 1)\r\n3) XOR the two sets of bits\r\n   xor = (set1 ^ set2) \r\n4) Put the xor bits back to their original positions. \r\n   xor = (xor << p1) | (xor << p2)\r\n5) Finally, XOR the xor with original number so \r\n   that the two sets are swapped.\r\n   result = x ^ xor<\/pre>\n[ad type=”banner”]\n
Implementation:<\/strong><\/p>\n
 
 c<\/span> <\/div> 
#include<stdio.h> int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n){    \/* Move all bits of first set to rightmost side *\/    unsigned int set1 =  (x >> p1) & ((1U << n) - 1);     \/* Moce all bits of second set to rightmost side *\/    unsigned int set2 =  (x >> p2) & ((1U << n) - 1);     \/* XOR the two sets *\/    unsigned int xor = (set1 ^ set2);     \/* Put the xor bits back to their original positions *\/    xor = (xor << p1) | (xor << p2);     \/* XOR the 'xor' with the original number so that the        two sets are swapped *\/    unsigned int result = x ^ xor;     return result;} \/* Drier program to test above function*\/int main(){    int res =  swapBits(28, 0, 3, 2);    printf("\\nResult = %d ", res);    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Result = 7<\/pre>\n
Following is a shorter implementation of the same logic<\/strong><\/p>\n
\n
\n\n\n\n
\n
\n
int<\/code> swapBits(unsigned <\/code>int<\/code> x, unsigned <\/code>int<\/code> p1, unsigned <\/code>int<\/code> p2, unsigned <\/code>int<\/code> n)<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/* xor contains xor of two sets *\/<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>unsigned <\/code>int<\/code> xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/* To swap two sets, we need to again XOR the xor with original sets *\/<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>return<\/code> x ^ ((xor << p1) | (xor << p2));<\/code><\/div>\n
}<\/code><\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n[ad type=”banner”]\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Swap bits in a given number – Bit Algorithm – Given a number x and two positions (from right side) in binary representation of x, write a function that swap<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74852,83566],"tags":[75277,75107,75266,75267,75115,75285,75102,75114,75099,75110,75292,75289,75282,75083,75079,75088,75269,75263,75279,75276,75268,75112,75111,75286,75274,75278,75109,75270,75272,75098,75273,75281,75283,75089,75287,75275,75104,75265,75291,75264,75293,75271,75284,75280,75288,75118,75086,75290],"class_list":["post-25773","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-bit-algorithms","category-swap-bits","tag-2-power-32-value","tag-32-bit-word","tag-binary-operation","tag-binary-operator-in-c","tag-bit-manipulation","tag-bit-manipulation-programs-in-c","tag-bit-number","tag-bit-reversal","tag-bit-table","tag-bitcount","tag-bits-library","tag-bittricks","tag-bitwise-logical-operators","tag-bitwise-operations-in-c","tag-bitwise-operator-in-c","tag-bitwise-operator-in-c-example-programs","tag-bitwise-operators","tag-bitwise-operators-in-c","tag-bitwise-operators-in-c-with-examples","tag-bitwise-operators-in-embedded-c","tag-bytes-table","tag-c-bit","tag-c-byte","tag-c-language-bits","tag-c-language-shift-operator","tag-c-programming-bits","tag-c-xor","tag-first-in-math-hack","tag-flip-c","tag-for-bit","tag-little-endian-converter","tag-magic-bit","tag-masking-in-c","tag-nextbit","tag-order-of-bytes","tag-reverse-bit","tag-set-bit","tag-swapping-program-in-c","tag-twiddle","tag-unsigned-int-in-c","tag-what-is-bitwise-operator","tag-xor-0","tag-xor-algorithm","tag-xor-coding","tag-xor-encryption-c","tag-xor-operation-in-c","tag-xor-operator-in-c","tag-xor-table"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25773"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25773\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}