2

For example, taking the number x=74, which in boolean is 1001010 . I denote x_bar as x_bar= 0110101. Here we see that x_bar has more ones.

Aayush Soni
  • 39
  • 3
    So the numbers of ones in $\bar{x}$ is exactly the number of zeros in $x$, right? So why do we need $\bar{x}$? Therefore, a better title (better because it is immediately apparent what you are asking about without having to try to comprehend what x bar is) would be something like "Efficient way to determine if a binary expansion of an integer (?) has more ones or zeros". – ViktorStein Sep 09 '19 at 17:57
  • Also, please read the tag descriptions before tagging. Here one can clearly see that this tag is inappropriate. – ViktorStein Sep 09 '19 at 17:58
  • https://oeis.org/search?q=0%2C1%2C1%2C2%2C1%2C2%2C2&language=english&go=Search – David P Sep 09 '19 at 18:00
  • Here, "efficiently" doesn't seem to be a mathematical but more a computing term (how do I implement it efficiently) so this might be the wrong forum to ask this... – ViktorStein Sep 09 '19 at 18:04
  • 1
    Minor comment: Assuming that our numbers $x$ and $\overline{x}$ use $k$ digits in their binary expansions, then $x+\overline{x} = \sum_{i=0}^{k-1} 2^i = 2^k-1$. So we can compute $\overline{x} = 2^k-1-x$ without converting $x$ to binary. – Michael Sep 09 '19 at 18:16
  • 1
    Unfortunately, given the number of binary digits $k$, I cannot think of a more efficient algorithm than just progressively computing the binary digits of $x$ (from right-to-left), stopping early if we learn that either the number of 1s or the number of 0s is larger than $k/2$. – Michael Sep 09 '19 at 20:27
  • Can't you just sum the digits and if the sum exceeds $\lceil\log_2(n)\rceil$, which is the number of digits in the base-2-expansion of $n \in \mathbb{N}$, there are more ones? – ViktorStein Sep 10 '19 at 23:21

1 Answers1

0

The closer to a power of $2$ the number $x$ is "from below", the more ones it has. You can compute the distance $x$ has to the next power of $2$ by finding $2^{\lfloor\log_2x\rfloor+1}-x$.

For example, $60$ is $4$ away from the next power of $2$. Indeed, $2^{\lfloor\log_260\rfloor+1}-60=4$.

So a possible solution is to compute the distance for $x$ and $\bar x$, and see which is smaller. I'm not sure how you're computing $\bar x$ (in particular, how do you deal with leading zeros, are they fixed length?)

Luke Collins
  • 8,748
  • 1
    Does this cope with the case such as 47, which is 101111 (has "lots of" ones) even if it is quite a lot further from the next power of 2 (64) than, say, 60? –  Sep 09 '19 at 18:21
  • $x=47=101111_2$ has 5 ones since it is closer to $64$ than $\bar x = 32 = 010000_2$. My method runs into problems with things like $x = 1110$, since $\bar x$ would just be $1$, and my method is suggesting that $1$ has ``more ones'' than $1110$. – Luke Collins Sep 09 '19 at 18:29
  • What my method is actually doing is establishing which has fewer zeros, rather than more ones. – Luke Collins Sep 09 '19 at 18:32
  • Ah, that is what you mean. Then, for $x=60$ the distance is $4$ and then $\bar{x}=3$ the distance is ... presumably ... $1$? –  Sep 09 '19 at 18:36
  • Exactly, that's what is happening. The problem is that "bar" as you have defined it is not involutionary, i.e., $\bar{\bar x}\neq x$. – Luke Collins Sep 09 '19 at 18:38