2

I got a matrix A, with the following bytes as rows:

11111110  (0xfe)
11111000  (0xf8)
10000100  (0x84)
10010010  (0x92)

My program reads a byte from stdin with the function sys.stdin.read(1). Suppose I receive the byte x 10101010 (0xaa). Is there a way using numpy to perform the multiplication:

>>> A.dot(x)
0x06 (00000110)

As A is a 4x8 matrix, compossed by 4 bytes as rows, and x is an 8 bit array, I was expecting to receive the (nibble 0110) byte 0000 0110 as a result of the multiplication A * x, treating bits as elements of the matrix.

If the elements of the matrix were treated as binary bytes, the result would be:

>>> A = np.array([[1,1,1,1,1,1,1,0],[1,1,1,1,1,0,0,0],[1,0,0,0,0,1,0,0],[1,0,0,1,0,0,1,0]])
>>> x = np.array([1,0,1,0,1,0,1,0])
>>> A.dot(x)%2
array([0, 1, 1, 0])
samba
  • 23
  • 1
  • 4
  • 1
    How exactly do you expect to get 0x06? Could you walk me through the manual steps (in your question) please? – Mad Physicist May 26 '17 at 14:36
  • Please add to your question. There is no way someone reading your question could have figured that out. – Mad Physicist May 26 '17 at 15:17
  • Please work through the actual steps in your question. – Mad Physicist May 26 '17 at 15:19
  • If A is 4x8, are the individual bits matrix elements? Are the nibbles matrix elements (in which case A is 4x2)? How are you actually doing this? – Mad Physicist May 26 '17 at 15:24
  • @MadPhysicist. Yes I want to treat the bits as elements of the matrix. I wonder if this can be done with `numpy`. – samba May 26 '17 at 15:34
  • It sure can. Please make your question explicit instead of ambiguous. Can you show how you get the final answer, because I am getting 84 if I operate on just the bits. – Mad Physicist May 26 '17 at 15:38
  • The smallest representable size in numpy is one byte `uint8` I believe – romeric May 26 '17 at 15:41
  • @romeric. That is irrelevant. – Mad Physicist May 26 '17 at 15:44
  • since A is shape (4,8), and x is (8,), then `A.dot(x)` should be shape (4,), not a scalar. You haven't yet explained clearly what you meant by "treating bits as elements of the matrix". – wim May 26 '17 at 15:47
  • Specifically, I understand how you do the row-wise multiplication of A and x (I think), but I do not understand how you add the results of that together to get 0x06 (I get 4 or 84) using two different methods. Unless you are willing to explain that, I think your question is unanswerable. If you do explain it, I can have an answer for you in 2 minutes. – Mad Physicist May 26 '17 at 15:49

1 Answers1

0

1. Not using dot

You do not need to fully expand your matrix to do bitwise "multiplication" on it. You want to treat A as a 4x8 matrix of bits and x as an 8-element vector of bits. A row multiplication yields 1 for the bits that are on in both A and x and 0 if either bit is 0. This is equivalent to applying bitwise and (&):

>>> [hex(n) for n in (A & x)]
['0xaa', '0xa8', '0x80', '0x82']


10101010
10101000
10000000
10000000

Here is a post on counting the bits in a byte. bin(n).count("1") is probably the easiest one to use, so

>>> [bin(n).count("1") % 2 for n in (A & x)]
[0, 1, 1, 0]

If you want just a number, you can do something like

>>> int(''.join(str(bin(n).count("1") % 2) for n in (A & x)), 2)
6

2. Using dot

To use dot, you can easily expand A and x into their numpy equivalents:

>>> list(list(int(n) for n in list(bin(r)[2:])) for r in A)
[['1', '1', '1', '1', '1', '1', '1', '0'],
 ['1', '1', '1', '1', '1', '0', '0', '0'],
 ['1', '0', '0', '0', '0', '1', '0', '0'],
 ['1', '0', '0', '1', '0', '0', '1', '0']]
>>> list(int(n) for n in bin(x)[2:])
[1, 0, 1, 0, 1, 0, 1, 0]

You can apply dot to the result:

>>> np.dot(list(list(int(n) for n in list(bin(r)[2:])) for r in A),
           list(int(n) for n in bin(x)[2:])) % 2
array([0, 1, 1, 0])
Mad Physicist
  • 107,652
  • 25
  • 181
  • 264