how to identify odd 1's in a binary number

Question

hi , how to identify odd 1's in a binary number my binary numbers is, i.e every odd bit is a 1 in binary number

1 1 0 0 1 0 0 0 1 0   1  0 1  0  1   1  1 1  1  1  0  1  1  0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11010101010101111110110
11101101010101100011011
11111100110101010111101

i want get output what bit is a odd 1 one that one i get using basic regular expression the output each string like this

1 1 1  1  1 1  1  1  1
1 5 9 11 13 15 17 19 23

like this i want get output from each binary string

Answer 1

All you need to look at is the last digit.

If it's 1,the according decimal number is odd.

If it's 0, it is even.

Answer 2

If you want to know how to detect an odd binary number, you just need to look if the last digit is a 1 then it is odd.

With regex, the expression is:

1$

Or if you must match the entire string then:

^[10]+1$

But you don't need regex for this... in pseudo-code:

if right(string,1) == 1

This method is better than regex, because regex doesn't work backwards, so it has to go through the entire string before it gets to the end.

A right/end function can just look at the last character directly, which is of course simpler and faster.

Ok, tcl syntax for that is:

if {[string index $str end] eq 1}

If this isn't what you're asking:

1. Put more details into the question on exactly what you do want.
2. Mark accepted answers on some of your previous questions.

Answer 3

I interpreted the question as being "finding if a given binary number contains an odd number of 1's" **. This regex will match all binary numbers with an even number of 1's:

^0*(?:10*10*)*$

Negate the match result to get your intended result.

** I know, probably not very likely but hey....

Edit: validates against the OP's input as follows:

110010001010101111110110 - MATCH (even number of 1's)
11010101010101111110110  - NO MATCH (odd number of 1's)
11101101010101100011011  - MATCH (even number of 1's)
11111100110101010111101  - MATCH (even number of 1's)

Answer 4

Let's first consider a simpler problem: using regex to match unary string (containing only 1) that contains an odd number of 1. So we want to match 1(1), 111(3), 11111(5), …, but not the empty string (0), 11(2), 1111(4), …

To do this, you match pairs of 1, leaving exactly one 1 unpaired. The pattern is thus (also on rubular):

^(11)*1$

Now we can modify this basic pattern to accommodate the 0. We observe that:

• 0* can appear before the first 1
• 0* can appear after the last 1
• 0* can appear in the pairs

That is, we need to insert 0* at these 4 points:

  \/  \/
^(11)*1$
/\ /\

Thus the pattern is (see matches on rubular.com):

^0*(10*10*)*10*$

We can do some optimizations, e.g. making the capturing group non-capturing, or even atomic, and making the * possessive, but this pattern as is works and will not backtrack catastrophically.

References

• regular-expressions.info/Anchors: ^/$, Repetition: *

Answer 5

Assuming that each string represents a binary number in big-endian form (bits being numbered from zero, which refers to the last character of the string), determining if all the odd bits (i.e., bit#1, bit#3, bit#5, etc.) in the string is done by testing if the string matches this regular expression:

^[01]?(?:1[01])*$

To understand this, first let's simplify by assuming that we already know that all characters are either 0 or 1. Given that (and ignoring non-capturing trickiness), we could have written (in expanded form):

^ .? (1.)* $
A BB CCCCC D <- the key

That's an anchored match of the whole string (A and D) which is the empty string, or any digit (B) or any number of a 1 followed by anything (C, which puts the 1 in the “odd” position) or a digit before an even number of digits with 1 in the “odd” position (B followed by C). I've just converted that basic form to the more efficient and exact representation before it by restricting the alphabet of symbols ([01] for .) and using a non-capturing parenthesis ((?:…) instead of (…)).

If you're considering the first bit to be bit #1, you need this RE instead:

^1?(?:[01]1)*$

For little-endian bit strings, you need to "reverse the RE" (or use string reverse on the string to be matched and use one of the other matchers). The "reversed RE" for the little-endian bit#0-first form is:

^(?:[01]1)*[01]?$

For little-endian bit#1-first:

^(?:1[01])*1?$

Remember, with all of these regular expressions it is easiest to write them in Tcl by enclosing them in {curly} braces.

---

Demonstrating:

foreach s {
    110010001010101111110110
    11010101010101111110110
    11101101010101100011011
    11111100110101010111101
    1110111011111010111010
} {
    set matches [regexp {^[01]?(?:1[01])*$} $s]
    puts "$s [lindex {{doesn't match} matches} $matches]"
}

Produces this output:

110010001010101111110110 doesn't match
11010101010101111110110 doesn't match
11101101010101100011011 doesn't match
11111100110101010111101 doesn't match
1110111011111010111010 matches

Answer 6

Convert to gray code and check the lsb.