Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.

learn more… | top users | synonyms

0
votes
2answers
51 views

Mathematically get $n$th bit from integer

Most programming languages have functions for getting bits but I need to do it on a calculator so I need to understand how to do it mathematically. Basically I need a formula for getting the $n$th bit ...
1
vote
1answer
189 views

Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
0
votes
1answer
58 views

how do I assign -12 in base 10 to biased 32 in binary?

Not really sure how to approach this one. I understand how to convert decimal to hex and all that, but what is biased 32?
0
votes
1answer
50 views

Expressing as 1's complement

I have the problem: Express ( -43) as a word-length 1’s complement number 43 is in decimal. I understand how to convert to Hexadecimal and take the 2's ...
0
votes
1answer
154 views

Count number of binary relations between sets

He, I have following questions: We have sets $A$ and $B$, $\left | A \right | = m,\left | B \right | = n$. 1) How many binary relations are there from $A$ to $B$? 2) How many binary relations are ...
1
vote
0answers
323 views

Calculating minimum hamming distance of a code

We use hamming code of (7,4,3); Given 4 bits of information, we'll add 3 bits of parity, and one more parity bit for the 7-bits code. Given $x_3,x_5,x_6,x_7$ $x_1 = (x_3+x_5+x_7) \mod 2$ $x_2 = ...
1
vote
0answers
24 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
4
votes
1answer
2k views

How many bits needed to store a number

How many bits needed to store a number $55^{2002}$ ? My answer is $2002\;\log_2(55)$, is it correct?
2
votes
0answers
48 views

Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
0
votes
2answers
258 views

creating a Binary tree based on a prefix expression

I want to find the value of a the prefix expression -/+8,10,2*3,2 and build its binary tree I am trying to learn this for a math course, but have absolutely no clue ...
2
votes
1answer
39 views

Powers of 10 in binary expansion

I noticed an interesting pattern the other day. Let's take a look at the powers of 10 in binary: $10^0$ = 1 = 1 b $10^1$ = 10 = 10 10 b $10^2$ = 100 = 1100 100 b $10^3$ = 1000 = 111110 1000 b ...
1
vote
2answers
48 views

Binary concatenation

In decimal, I have the numbers 4 and 5 for example. I want to concatenate them into the number 45, but then in binary. In decimal, it's just a matter of sticking the numbers together, but I need to do ...
0
votes
1answer
51 views

Conditions for a decimal to be convertible to binary

All natural numbers (Base 10) can be converted to binary. No problem. But what about fractional numbers? All cannot be converted (finite expansion). Example: $0.625$ can be converted but $0.11231$ ...
1
vote
3answers
87 views

How to fast convert from Octal to Hexadecimal

There has been a similar question before: How to convert a hexadecimal number to an octal number? But, in my case I need an Algorithm to directly convert a number from Octal to Hexadecimal and back ...
0
votes
1answer
26 views

Binary to Hexadecimal number

I know how to convert 0101 | 0111 in which the 0101 gives me 5, and ...
3
votes
1answer
193 views

On a scale of 1 to 10, how likely is it that this question is using binary? [closed]

I just read this interesting xkcd strip: At first I thought it was funny, but as I got to ruminate a little over it, I was surprised to be unable to find an answer. As Karolis Juodelė pointed out, ...
-1
votes
1answer
213 views

Inverse of binary matrix

I have tried creating an inverse of a binary matrix using the identity matrix method. Have an identity matrix alongside the square matrix and perform all the operations to convert the square matrix to ...
0
votes
3answers
44 views

converting to octal, hexadecimal and binary

Revising for an exam - could someone explain to me how you can convert an ordinary numbers to octal, hexadecimal and binary would be appreciated
4
votes
1answer
98 views

XOR of Three Integers

How would you prove the following: Given three non-negative integers $a, b, c$; if $a \oplus b \oplus c = 0$ then $(a - k) \oplus (b - k) \oplus (c - k) > 0$ for any $0 < k \leq min(a, b, c)$ ? ...
2
votes
2answers
363 views

Binary Logistic Regression Model Processing

Thanks for showing interest and wanting to help out. My aim is to develop a model that - as accurately as possible - predicts how entities in a population will either cooperate or defect, as a % of ...
2
votes
1answer
65 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
0
votes
1answer
57 views

Compressing a short list of very large numbers?

Suppose that we are dealing with integers drawn from a random uniform distribution, on the range $[1 , 2^{30}]$. Is it possible to effectively compress a short list of random numbers, say $2^4$ ...
28
votes
10answers
4k views

In plain English, why does conversion from hexadecimal to binary work so cleanly?

Why does the trick of taking the binary representation of each digit and simply concatenating them work? e.g. 0x4E == 0100 ...
1
vote
4answers
76 views

Find the number of 1s or 0s in binary representation of a number

What is the number of 1s in the binary representation of $$3*512 + 7*64 + 5*8 + 3$$ Is there any shortcut for finding the number of 1s and 0s in a binary number which has been factored as above?
3
votes
2answers
73 views

How do we know $p/q$ can be expressed as a terminating fraction in base $B$ only if prime factors of $q$ are prime factors of $B$?

On cs.stackexchange I asked a math question: How to demonstrate only 4 numbers between two integers are multiples of .01 and also writable as binary. Yuval Filmus answered with a explanation ...
0
votes
2answers
75 views

Use strong induction to prove number of vertices on complete tree is $2l-1$

Can someone help me construct this proof using strong induction? Use strong induction on $l$ to show that for all $l \geq 1$, a full binary tree with $l$ leaves has $2l-1$ vertices total.
2
votes
1answer
82 views

Why do XOR and other operators on binary variables qualify as linear?

I never fully understood why is the operation $\oplus: \{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}^n$ considered linear ? I am well aware of the definition of linearity on real numbers, and I ...
1
vote
1answer
92 views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Stick-weak Ordering term. I have this requirement while sorting strings. Thanks.
5
votes
1answer
152 views

Generating Function for Binary String Question

The following is an assignment question I have been trying to work out for quite some time. Let $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$, where $c_{n,k}$ is the number of binary strings of ...
0
votes
1answer
343 views

Binary string with even and odd number of 1s [duplicate]

How could it be shown that the number of binary string of length k with an even number of 1s is the same as those with an odd number of 1s. Eg. for $k = 3$ : Binary string length 3 with even amount ...
0
votes
2answers
152 views

How to convert an infinite binary fraction into a decimal fraction

I am asked to write the infinite binary fraction $0.(1011)$, where the $1011$ is the repeating part, as a $\frac pq$ fraction. What are the steps to do this? EDIT: If $0.(1011)$ was in base 10, I ...
2
votes
1answer
41 views

Computation and Elimination (Solution Verification)

Consider a set B (of binary strings) given by the introduction rules: \begin{equation} \frac{}{\epsilon :B} \quad \frac{a:B}{s_{0}(a):B} \quad \frac{a:B}{s_{1}(a):B}\end{equation} ...
0
votes
0answers
29 views

Search L leaves smaller than node N

So in my binary $kd$-tree I have a node $N$. Now I search for the number of leafs $L$ "on the left" side of $N$ (this includes the left child branch of $N$ and all parents where the node is a right ...
0
votes
1answer
101 views

Binary multiplication

Please don't be to harsh with me if you think that this is to simple, I just don't understand it. I been trying to follow this site(Method 2) to solve simple multiplication of $3 * 3 = 9$, but it ...
3
votes
3answers
1k views

A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?

In this earlier question, the OP asks for a proof of the statement Every natural number not of the form $2^k$ for some natural number k can be written as the sum of two or more consecutive ...
1
vote
2answers
60 views

Binary number theory

I want to know if there exists some book about "Binary number theory", I'm interesting in this because there many problems of ICPC about this topic. Thanks in advance
3
votes
1answer
98 views

Lower bound on a number theoretic function

Let $n$ be a positive odd integer, let $$n_j = \Bigl\{\frac{n}{2^{j+1}}\Bigr\}\,,$$ where $\{x\}$ denotes the fractional part of $x$, and finally let $k = \lceil \log_2 n\rceil$. Consider the ...
2
votes
1answer
62 views

Calculating 6 decimal digits of $3^{\sqrt2}$ using a calculator.

How can we calculate $3^{\sqrt2}$ to 6 decimal digits, using only a semi-basic calculator (Which has the square root too) and a pen and paper? I asked this question from my teacher and he ...
0
votes
0answers
27 views

How to convert decimal number to base -10 [duplicate]

How to convert from decimal (base 10) number to base -10? For example, $$ -44 \mapsto 56_{-10}, $$
1
vote
2answers
218 views

converting decimals to base negative-10

I have a decimal (base $10$) number, $44$, and would like to convert it to base $-10$. I know how to convert $$ 164_{-10} \mapsto 44_{10}, $$ but not the other way around.
1
vote
2answers
850 views

Maximum run of zeros in a $n$-bit binary string

I came to know that, in a random string, one expects the longest sequence of zeros to be roughly of length $\log n$. I want to be able to prove this. For this I need to know the probability that the ...
0
votes
1answer
33 views

Dyadic rationals representation in the computer memory.

So I know what a dyadic rational is and that is represented with a finite number of binary digits in memory. The idea is that I want an explanation why is it represented in this way ? Thank you.
0
votes
1answer
71 views

binary division and remainder

Q=A/B , Q is a real number expressed as a pair of 8 bits: most significant 8 bits for the integer part least significant 8 bits for the fractional part the number is unsigned for example: 0 0 1 ...
2
votes
3answers
83 views

Finding element in binary representation of $GF(2^6)$

I got the following task: Let $F = GF(2^6 )$ be K[x] modulo the primitive polynomial $h(x) = 1 +x ^2 +x ^3 +x ^5 +x ^6$ , and let $\alpha$ be the class of x. I have a table with the binary ...
1
vote
2answers
44 views

Binary Numbers system for Programming

So, the maximum number 1 byte (8 bits) can have is 255, so does that mean 255 combinations of 0 & 1 in the 8 places?
2
votes
2answers
147 views

Hexadecimal to Octal and Vice Versa

Convert Hexadecimal number to Octal - $(FD56.52A)_{16}$ to octal My answer - $(176526.2452)_8$ Convert Octal to Hexadecimal $(37.27)_8$ My answer - $(1F.5C)_{16}$. Correct or incorrect? Please ...
1
vote
2answers
80 views

Arithmetic operation of binary numbers - Is my answer correct?

Does the arithmetic operation - 102 (base 10)- 39 (base 10), represented in 8-bit, when converted to binary have an overflow or underflow? My Ans - It has no problem. I mean there is neither ...
5
votes
1answer
156 views

Efficient division using binary math

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication ...
0
votes
1answer
69 views

Inserting values left to right in a binary search tree

What does it mean to build a binary search tree by inserting values from left to right starting from an empty tree? The "left to right" part confuses me..I know how to build one by normally inserting ...
1
vote
1answer
74 views

running time of a multiplication algorithm

Here is a multiplication algorithm: given inputs x and y, add x to itself y - 1 times: z = 0 while y > 0: z = z + x y = y - 1 return z What is the running time of this algorithm? Is it ...