Patterns in Binary Numbers

Question

Consider an n-bit binary number in the following form:

b_n−1b_n−2b_n−3...b₀

Each b_i is a single bit in the n-bit binary number. Each b_i has one of two possible values: 0 or 1. An example of a 6-bit binary number is: 110011. Inside the computer, integers are represented as binary numbers. For example, the integer 43 can be represented by the 6-bit binary number: 101011. In this part, we will make use of an m-bit binary pattern that is constructed by taking the first m-bits of the repeating sequence 101010. . . . For example, for m equal to 3, the binary pattern is: 101. For m equal to 6, the binary pattern is: 101010. For m equal to 1, the binary pattern is: 1.

Write a C program that reads integers n and m as input, and then prints out all n-bit binary numbers that contain the m-bit pattern. The binary numbers must be printed in ascending order. You are not allow to use strings, arrays or recursion for this question. Any program that uses strings, arrays or recursion will receive a grade of 0. Your program may assume that n will be a natural number less than or equal to 30, and that m will be a natural number less than or equal to n.

A sample output for this program is:

Enter an integer n: (5)
Enter an integer m: (3)
00101
01010
01011
01101
10100
10101
10110
10111
11010
11011
11101

I'm a beginner in programming and I've gotten this assignment to do. I understand how the program is going to work but I'm not too sure how to go about it. Can anyone help me out and post a solution to this so I can run through it and see how it works. Thanks

Answer 1

How to program, a two-step process:

1. Solve the problem yourself.
2. Make the computer do what you did.

You should at least post your "I understand how the problem is going to work" so that you can be guided towards "how to go about it".

---

I'm gonna pretend I don't know C for now.

J

f=:4 :'#:(#~([:+./(#.y$1 0)=(2^y)|<.@-:^:(i.x))"0)i.2^x'

Haskell

f n m = filter bits [0..1^n-1] where
    p = foldl ((+).(*)2) 0 $ take m $ cycle [1,0]
    bits = elem p . map (`mod` 2^m) . takeWhile (/= 0) . iterate (`div` 2)

Answer 2

Figure out what the value of M represents with the repeating sequence. (e.g. 3 = 101) Chop off the tail end of the number you're testing one step at a time with x/2 or x >> 1 and see if the length of remainder you care about matches. (test % (1 << m) == 101)

Edit: In python...

binary = lambda i, c = (lambda i, c: i and (c(i >> 1, c) + str(i & 1)) or ''): c(i, c)
def SilentsHomework(M, N):
 count, base = 0, int(''.join([str([0,1,0][(-1)**x]) for x in xrange(N)]),2)>>(N-M)
 for i in xrange(1,1<<N):
  orig_i_nal = i
  while i:
   if i%(1<<M)==base: count += 1; print binary(orig_i_nal); break
   else: i >>= 1

Strings, check. Arrays, check. Recursion, nope :(

Answer 3

left shift (<<) and or (|) are your friends for solving this.

Answer 4

I can give you some clues. Only clues. Because answers for all homeworks would be like a girl in bikini. You have to guess a lot.

To generate the m bit pattern, use a loop starting from 0 to m.

for( i = 1; i <= m; i++)
{
    Pattern = ( Pattern * 2 ) + ( i % 2 )
}

To generate an n bit number in ascending order, you should write a loop starting from 1 to 2^n.

for( i = 1; i < pow( 2, n ); i++ )

Next step is to check whether the Pattern is present in i. This SO article will help you for that.