Tag Info

New answers tagged

1

Half of the question was “Can I get $M$ only knowing $P$?” The answer to this question is no, even under the strong restriction that the original two numbers have the same number of binary digits (known) and both begin and end with a $1$. Suppose there are two 11-bit binary numbers $a$ and $b$ whose product is $P=ab=2027025_{10}$. What is the “mirror ...


1

I will assume both numbers have the same length. If $A=a_n2^n+a_{n-1}2^{n-1}+\cdots +a_0$, $B=b_n2^n+b_{n-1}2^{n-1}+\cdots +b_0$ then $$A\times B=(a_0b_0)+(a_0b_1+a_1b_0)2+\cdots (a_nb_n)2^{2n}$$ The product of the reversals would be $$A_R\times B_R=(a_nb_n)+(a_nb_{n-1}+a_{n-1}b_n)2+\cdots (a_0b_0)2^{2n}$$ In other words, don't carry while multiplying. Then ...


1

Consider $2^n = 100 \ldots 0 \times 100 \ldots 0$, in binary, where each number has length $n/2$. If you reverse the digits of these two factors you get $1 \times 1 = 1$. So there is no way to recover $n$.


2

An $n$-bit number $a$ is a number with $2^{n-1}\le a<2^n$. Then for $a^k$ we have $2^{kn-k}\le a<2^{kn}$, i.e. $a^k$ has at least $kn-k+1$ and at most $kn$ binary digits. Especially the cube of a 256 bit number has between 766 and 768 bits.


0

You have to be more carefull with how exactly you define your binary representation. The basic idea is to represent some value $x$ as $$ x = (-1)^s \cdot m\cdot 10^e $$ and store it as a triple $(s,m,e)$ where one bit is allocated to $s$, $8$ to $m$ and $4$ to $e$. The format of $s$ is simple enough - $1$ means the value is negative, $0$ means it's ...


0

Check your calculation: 00101011.1010 + 10110101.1000 = 11100001.0010


0

You just need 6 states: initial state 1, final state 6. $1 \xrightarrow{0} 2 \xrightarrow{0} 4 \xrightarrow{1} 5 \xrightarrow{1} 6 \qquad 1 \xrightarrow{1} 5 \qquad 2 \xrightarrow{1} 3 \xrightarrow{0} 5$


6

For universality, you needto be able to produce $1$ even when all inputs are $0$, hence $0\circ 0=1$. Similarly, $1\circ1=0$. This leaves us with only four functions. Two of these ($\neg A$ and $\neg B$) are in fact unary, so indeed only NAND and NOR remain.


0

"Solve 3a+2b+c=5 over GF(2)" (You're just wanting to restrict the variables to the finite field with two elements.)


0

Sorry, I'm no good at drawing diagrams so you will have to draw one yourself. State $q_0$ is the initial state and $q_4,q_7,q_9$ are accepting states. $$\matrix{\hbox{state}&0&1\cr q_0&q_1&q_8\cr q_1&q_2&q_5\cr q_2&q_{10}&q_3\cr q_3&q_{10}&q_4\cr q_4&q_{10}&q_{10}\cr q_5&q_6&q_{10}\cr ...


0

I try to offer my suggestion and it should not be taken as solution because I am not sure it is correct or not. Notation: [n] is called the greatest integer function. It is used to extract the integral part of the number n. Example: [4.78] = 4. Step-1 … Convert 0.375 to binary first. --------- Multiply 0.375*2 = 0.75----record the result of [0.75] as A, ...


12

Trick: divide consecutively the quotients by $\;5\;$ and keep aside the residues : $$\begin{align*}\frac{727}5=145+\frac25\longrightarrow& \color{red}2\\ \frac{145}5=29\longrightarrow&\color{red}0\\ \frac{29}5=5+\frac45\longrightarrow&\color{red}4\\ \frac55=1\longrightarrow&\color{red}0\\ ...


8

You have to keep dividing by $5$ and write all the remainders. So $$727 = 5\cdot 145 + 2$$ $$145 = 5\cdot29 + 0$$ $$29 = 5\cdot5 + 4$$ $$5 = 5\cdot1 + 0$$ $$1 = 5\cdot0 + 1$$ Write all the remainders in reverse: $10402$ And ta-da! There is your answer :-)


1

The trick is to realize that \begin{align*} 727 &= 625 + 0*125 + 4*25 + 0*5 + 2 \\ &= 5^4 + 0 *5^3 + 4*5^2 + 0*5^1 + 2*5^0. \end{align*} So the answer is $10402$.


12

You need to count in terms of $5^0, 5^1, 5^2, 5^3$ and $5^4$, not in term of $100 ,10$ and $1$. Start by the highest power of $5$ smaller than your number, i.e. $5^4=625$ here, and check how much you can multiply it without exceding (this will be a number in $1,2,3,4$). Take the leftover (base 10, 727-625=102) and repeat until you reach $0$. You should ...


2

After the point, it goes like $16^{-1}$, $16^{-2}$ etc. Therefore, $(15C.38)_{16}$ can be converted by doing the following: $1 \times 16^2 + 5 \times 16^1 + 12 \times 16^0 + 3 \times 16^{-1} + 8 \times 16^{-2}$. Another method is, writing every digit as 4-bit binary string and than converting those to decimal. i.e. $(0001$ $0101$ $1100$ . $0011$ ...


1

We have $15C_{16}=348_{10}$. The fractional part is $0.38_{16}$ which is $(3\times 16^{-1})+(8\times 16^{-2})=0.21875$. So $15C.38_{16}=348.21875_{10}$.


2

After the "radix" point (the dot), we can just divide each integer in place $i$ counting from the left by $16^{i}$. So $0.36_{16} = 3/16+6/16^2$. This generalizes to all bases.


2

Suppose there are $2n$ digits to fill. (The problem is clearly impossible if the number of digits is odd.) Once we have chosen the location of the $n$ zero digits the position of the ones digits will be uniquely determined. It follows that the number of strings of the form you are looking for is the number of ways to choose $n$ objects from a set of $2n$ ...


2

Pick $n$ of the $2n$ digits to put one's in: $$\binom{2n}{n}=\frac{(2n)!}{(n!)^2}$$


1

For a bitstring $a$, you can consider its graph $$\newcommand{\graph}{\operatorname{graph}}\graph a := \{ (k, a_k) : k \in [n] \} \subset [n] \times \{0,1\}.$$ Here $[n] := \{1,2,\dots, n\}$. (For a formal set theory point of view, $a$ and $\graph a$ are actually the same object.) Then your condition reads $$\graph b \subset \bigcup_{a \in A} \graph a.$$


1

Your "bit combination" vectors can be interpreted as so-called choice functions in the context of set theory. Maybe that is not exactly what you're asking for, but the similarity is overwhelming. More precise: Let us at first transform your set $A$ into $n$ sets $A_{i}$, where each set $A_{i}$ contains the $i$-th bits of all vectors in $A$. For example ...


0

If the problem is counting the binary matrices $M$ (all entries zero or one) that are positive definite symmetric as real matrices, the answer seems to be only the $n \times n$ identity matrix for each $n$. Certainly the diagonal must consist of ones, else $e_i^T M e_i$ would be zero for some standard basis vector $e_i$. If some off-diagonal matrix entry ...



Top 50 recent answers are included