Быстро и карсиво разложить число по степеням (-2)

как?

А деление на -2 в цикле чем не нравится?

Если по степеням 2, то битовыми проверками и сдвигами.

"деление на -2 в цикле"? не догнал, виноват

можно примерчик для например числа 13?

-Added 13.04.08, 15:32

Цитата andriano @ 13.04.08, 15:18

Если по степеням 2, то битовыми проверками и сдвигами.

именно по минус 2

13

div  mod
-6   1
3    0
-1   1
1    1
0    1

остатки снизу вверх записываем
11101

Сообщение отредактировано: MBo - 13.04.08, 15:38

если на пасе, то

n:=13;
 
repeat
writeln(n mod -2);
n:=n div -2;
 
until n=0;

выдает

1
0
1
-1

В паскале mod возвращает результат со знаком равным знаку первого операнда. А тебе нужен mod, возвращающий только неотрицательные остатки.

ихдежеговзять? не хочется лепить кучу условий (если это минус, а это плюс , то ... и т.д.)

для 2345 ответ моего 0-кода еще страшнее:

1
0
0
-1
0
-1
0
0
1
0
0
-1

Правильный ответ: 1100101111001

Цитата darcus @ 13.04.08, 17:37

ихдежеговзять?

Написать Там же всего одна строчка.

function modNeg2(a: integer): integer;
begin
  modNeg2 := abs(a mod (-2));
end;

Аналогично "исправляем" div, так как теперь перестало выполнятся тождество (a div b)*b + (a mod b) = a

сенькс однозначно. Получилось типа так:
Ответ собираем в строку s (и в нужном порядке):

def roo(n):
    if n==0:
        return '0'
    s=''
    while n!=0:
        m=n%-2
        n=n/-2
        if m==0:
            s='0'+s
        else:
            s='1'+s
            if m==-1:
                n=n+1
    return s
 
print roo(input())

Сообщение отредактировано: darcus - 18.04.08, 03:20

Ё моё, подробности: задача сводится к изменению системы исчисления из десятичной в двоичную.
Решено-перерешено.

только основание системы счисления < 0

Реализация на С#:
****************************************
int m=77855442;
Console.WriteLine(Convert.ToString(m,2));
****************************************
выдает типа 100101000111111101011010010
press any key......

и никаких тебе условий......

kiryshka, ну хотя бы заголовок темы нужно читать
Основание (-2).

да какая разница? остаток от деления что на -2, что на 2 один и тот же.....(если не учитывать отрицательный результат)

А частное?

А нет ли способа "мгновенно" найти разложение для -Z из разложения для +Z ?

+123456789
 
11000101011001101110100010101
 
 
-123456789
 
1001111001000111011100111111
 
 
+345634295858585858375757682846739644999374848484657282929292929234215673853
 
1110001001110001101000001100100001001010101011100110110100001111011010011000111111100
1110111010100101000101000000011110001000011011101011010000110101111010001011010000001
1100101000010011000001011010110001010111000000111100101001001011110000000001101
 
 
-345634295858585858375757682846739644999374848484657282929292929234215673853
 
1101001101101000011100000010110001101111111111010001001110000010100111000100110101010
1101110111110111100111100000000101001100000111011100111000001110010111001100111000001
10101111000110001000011001110010011111101000000010101111011011001010000000000111

Цитата albom @ 17.04.08, 19:33

А частное?

опять таки...-(частное)%-2 дает положительный результат, как я понял то что нужно
(частное)%2 то же самое
(частное)%-2 дает отрицательный результат и мы пренебрегая минусом записываем положительное число
-(частное)%2 -то же самое

в результате имеем, что в любом случае мы пренебрегаем отрицательным результатом..............

итого, как бонус мы получаем 2 = -2 !

Цитата darcus @ 18.04.08, 14:51

А нет ли способа "мгновенно" найти разложение для -Z из разложения для +Z ?

Нет, и не может быть, так как сложность алгоритма не может быть меньше битового размера выхода.

А вообще, знак в этой системе счисления у числа можно изменить двумя способами.
Первый состоит в том, что мы складываем число с самим собой сдвинутым влево на один разряд.
Второй способ состоит в вычитании из нуля нашего числа.
Но учти, что даже сложнение в этой системе несколько необычно, так как сумма двух битов может порождать до двух битов переноса. Например,

 1 + 1     = 110
11 + 1     = 0
 1 + 1 + 1 = 111

Цитата kiryshka @ 18.04.08, 19:29

опять таки...-(частное)%-2 дает положительный результат, как я понял то что нужно
(частное)%2 то же самое
(частное)%-2 дает отрицательный результат и мы пренебрегая минусом записываем положительное число
-(частное)%2 -то же самое

в результате имеем, что в любом случае мы пренебрегаем отрицательным результатом.

А какое отношение все это имеет к исходной задаче?

Цитата albom @ 19.04.08, 08:04

А какое отношение все это имеет к исходной задаче?

может я что то недопонимаю?
10:

10%-2=0
-5%-2=1
2%-2= 0
-1%-2=1

Цитата kiryshka @ 19.04.08, 11:13

может я что то недопонимаю?

Вероятно, да. А именно, как разделить одно число на другое.
Правильно деление будет выглядеть так:

10 / -2 = -5 rem 0
-5 / -2 =  3 rem 1
 3 / -2 = -1 rem 1
-1 / -2 =  1 rem 1
 1 / -2 =  0 rem 1

Правильный ответ: 10₁₀ = 11110_-2, а вовсе не то, что у тебя получилось.

сорри

Прошу высказываться. только для положительный целых чисел

#include <stdio.h>
#include <math.h>
 
int binarinegativ(int X){
    int d =2,B,C,X1;
    X1 = X;
    printf("foundation (2) %d = %0.4X\n",X,X);
    do{ B = X & d;
        d *= 2;
        if(B) X += d;
        C = (int)( log(X)/log(2) ) ;
        C = (int)pow(2,C);
    }while(d < C );
    printf("foundation (-2) %d = %0.4X\n",X1,X);
    return X;
}
 
int main(void){
    int V;
    while(1){
     puts("Input digit, 0 fo exit\n");
     if(!V) break;
     scanf("%d",&V);
     binarinegativ(V);
    
     getchar();
}
    return 0;
}

Цитата AndreyK @ 20.04.08, 11:00

Прошу высказываться. только для положительный целых чисел

Не работает ни для положительных, ни для отрицательных.

Кстати, можешь попробовать сделать через формулу Шреппеля:

B = (N xor 0b10101010101010...) - 0b1010101010....

это была попытка сделать *что*?

Приношу свои звинения за предыдущий вариант.
Этот, вроде, работает.
Раскладка натурального числа по основанию(-2)
X = k*(-2)ⁱ; где k 1 или 0,i - нумер разряда(нумерация от младшего к старшему начиная с нуля).
Опять же прошу высказываться.

#include <stdio.h>
#include <math.h>
 
int binarinegativ(int X){
    int d =2,B,C,X1;
    X1 = X;
    printf("foundation (2) %d = %0.4X\n",X,X);
    do{ B = X & d;
        if(B) X += (d*2);
        d *= 4;
        C = (int)( log(X)/log(2) ) ;
        C = (int)pow(2,C);
    }while(d <= C );
    printf("foundation (-2) %d = %0.4X\n",X1,X);
    return X;
}
 
int main(void){
    int V;
    while(1){
     puts("Input digit, 0 fo exit\n");
     if(!V) break;
     scanf("%d",&V);
     binarinegativ(V);
    
     getchar();
}
    return 0;
}

Цитата AndreyK @ 21.04.08, 12:22

Этот, вроде, работает.

Увы, и этот вариант не работает. Неужели так сложно самостоятельно проверить хотя бы первые десять натуральных чисел? Ведь уже на них выдается неверный ответ.

Цитата AndreyK @ 21.04.08, 12:22

Опять же прошу высказываться.

Я не очень понимаю смысл выкладывать вот эти исходники.
Во-первых, это не алгоритм, а код, причем код очень непонятный, который к тому же не работает.
Во-вторых, в этой теме уже приведено решение, даже есть работающий исходник. Почему не сравниваешь свою реализацию с ним?
И в-третьих, просили разложить "Быстро и карсиво", а тут увы нет ни того, ни другого.

Короче, давай, испрявляйся по всем пунктам, и показывай, что у тебя там получилось