Author |
Topic: In-place Bit re-arrangement (Read 556 times) |
|
ThePriest
Newbie
Gender: 
Posts: 16
|
 |
In-place Bit re-arrangement
« on: Feb 28th, 2008, 9:17am » |
 Quote  Modify
|
This one is similar to the alternate in-place array rearrangement problem, posted a few days ago, but modified for a bit pattern.
You are given a number (either 32 or 64 bit)containing some bit pattern (or numeric value). You have to place all the 0s in even position and 1s in odd position and if suppose number of 0s exceed the number of 1s or vice versa then keep them untouched. Generalize your solution for an N bit number.
It has to be done in O(n) time, without several single loops (only one pass) and O(1)space.
For e.g.
Input Number: 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1
output number: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1
|
|
 IP Logged |
|
|
|
Ved
Junior Member
Gender:
Posts: 53
|
|
Re: In-place Bit re-arrangement
« Reply #1 on: Jan 26th, 2010, 12:24am » |
Quote Modify
|
{Sorry to resurrect a very old unanswered post}
Logic : We need to maintain two pointers – oddPtr which moves along the odd positions in the array and evenPtr which moves along the even positions. When we find an incorrect position, we swap this pointers and move along.
One interesting case is when one of the pointer moves past the last element, in that case, we have no way to compare the other pointer with. In this case, we simply swap one pointer with the other position.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: In-place Bit re-arrangement
« Reply #2 on: Jan 26th, 2010, 12:37am » |
Quote Modify
|
on Feb 28th, 2008, 9:17am, ThePriest wrote:if suppose number of 0s exceed the number of 1s or vice versa then keep them untouched. Generalize your solution for an N bit number.
|
|
Input Number: 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0
output number: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1
The extra 1s here, cannot be left untouched. They will be pushed towards one end.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print