Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Regular Expression for Binary Numbers Divisible by 5

Tags:

regex

binary

division

I want to write a regular expression for Binary Numbers Divisible by 5.
I have already done the regular expressions for Binary Numbers Divisible by 2 and for 3 but I couldn't find one for 5.

Any suggestions?

like image 458
The Beast Avatar asked Dec 26 '15 23:12

The Beast

People also ask

How do you know if a binary number is divisible by 5?

5 in base 4 is equivalent to 11. Now apply the rule of divisibility by 11 where you add all the digits at odd places and add all the digits at even places and then subtract one from the other. If the result is divisible by 11(which remember is 5), then the binary number is divisible by 5.

How do you make a number divisible by 5?

For a number to be divisible by 5, the only condition is that the digit at the unit place in the number must be either 0 or 5.

How do you know if a binary number is divisible by a binary number?

Efficient Approach: In the binary string, check for the last k bits. If all the last k bits are 0, then the binary number is evenly divisible by 2k else it is not evenly divisible.

What is the answer of divisible by 5?

A number is divisible by 5 if the number's last digit is either 0 or 5. Divisibility by 5 - examples: The numbers 105, 275, 315, 420, 945, 760 can be divided by 5 evenly.

1 Answers

(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*

Add ^$ to test it with regexp. See it working here.

You can build a DFA and convert it to regular expression. The DFA was already built in another answer. You can read it, it is very well explained.
The general idea is to remove nodes, adding edges. before

Becomes:

after

Using this transformation and the DFA from the answer I linked, here are the steps to get the regular expression:
(EDIT: Note that the labels "Q3" and "Q4" have been mistakenly swapped in the diagram. These states represent the remainder after modulus 5.) step1 step2 step3 step4 step5
like image 62
ndnenkov Avatar answered Oct 06 '22 23:10

ndnenkov
Sign in to Comment

Related questions

Regex match markdown link
regular expression split : FutureWarning: split() requires a non-empty pattern match
search with grep for words beginning and ending with
Regex to match words and those with an apostrophe
"range out of order in character class" in PHP regex?
C# Regex - How to remove multiple paired parentheses from string
Whole-word match only in Django query
Excluding some character from a range - javascript regular expression
Find and Replace Strings in Documents Efficiently
Phabricator linter can't find any lintable paths
Finding all occurrences of alternating digits using regular expressions
How to parse CSV data that contains newlines in field using JavaScript
Algorithm to find the most repetitive (not the most common) sequence in a string (aka tandem repeats)
Regex for a pattern XXYYZZ
Ruby gsub / regex modifiers?
C# - Regex - Matching file names according to a specific naming pattern
Search/Replace in Vim
Trying to split string into single words or "quoted words", and want to keep the quotes in the resulting array
Replace non alphanumeric characters except some exceptions python
Regex for ISO 8601 durations

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!