تقسيم عدد بنسبة 3 دون استخدام * ، / ، + ، - ، ٪ المشغلين
https://stackoverflow.com//questions/11694546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
كيف تقسم رقما على 3 بدون استخدام *, /, +, -, %, مشغلي?
قد يكون الرقم موقعا أو غير موقع.
المحلول
هذا هو وظيفة بسيطة الذي يؤدي العملية المطلوبة.ولكنه يتطلب + المشغل ، لذلك كل ما عليك القيام به هو إضافة القيم مع مشغلي بت:
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
كما علق جيم هذا يعمل ، لأن:
n = 4 * a + bn / 3 = a + (a + b) / 3لذا
sum += a,n = a + b, ، وتكرارعندما
a == 0 (n < 4),sum += floor(n / 3);أي.1,if n == 3, else 0
نصائح أخرى
تتطلب الظروف الغبية حلا غبيا:
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE * fp=fopen("temp.dat","w+b");
int number=12346;
int divisor=3;
char * buf = calloc(number,1);
fwrite(buf,number,1,fp);
rewind(fp);
int result=fread(buf,divisor,number,fp);
printf("%d / %d = %d", number, divisor, result);
free(buf);
fclose(fp);
return 0;
}
إذا كان هناك حاجة أيضا إلى الجزء العشري ، فقط أعلن result كما double وإضافة إلى ذلك نتيجة fmod(number,divisor).
شرح كيف يعمل
- ال
fwriteيكتبnumberبايت (الرقم 123456 في المثال أعلاه). rewindإعادة تعيين مؤشر الملف إلى الجزء الأمامي من الملف.freadيقرأ بحد أقصىnumber"السجلات" التي هيdivisorفي الطول من الملف ، وإرجاع عدد العناصر التي قرأتها.
إذا كنت تكتب 30 بايت ثم قراءة الملف مرة أخرى في وحدات من 3 ، وتحصل على 10 "وحدات".30 / 3 = 10
يمكنك استخدام الجمعية المضمنة (POLLES)، على سبيل المثال، ل X86: (يعمل أيضا للأرقام السالبة)
giveacodicetagpre.(ملاحظة:انظر تحرير 2 أدناه للحصول على نسخة أفضل!)
هذه ليست صعبة كما يبدو ، لأنك قلت "بدون استخدام [..] + [..] مشغلي".انظر أدناه, إذا كنت تريد أن تمنع استخدام + حرف كل ذلك معا.
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
for (unsigned i = 0; i < by; i++)
cmp++; // that's not the + operator!
floor = r;
r++; // neither is this.
}
return floor;
}
ثم أقول: div_by(100,3) تقسيم 100 قبل 3.
تحرير:يمكنك الذهاب على محل ++ المشغل أيضا:
unsigned inc(unsigned x) {
for (unsigned mask = 1; mask; mask <<= 1) {
if (mask & x)
x &= ~mask;
else
return x & mask;
}
return 0; // overflow (note that both x and mask are 0 here)
}
تحرير 2:أسرع قليلا الإصدار دون استخدام أي مشغل الذي يحتوي على +,-,*,/,% الشخصيات.
unsigned add(char const zero[], unsigned const x, unsigned const y) {
// this exploits that &foo[bar] == foo+bar if foo is of type char*
return (int)(uintptr_t)(&((&zero[x])[y]));
}
unsigned div_by(unsigned const x, unsigned const by) {
unsigned floor = 0;
for (unsigned cmp = 0, r = 0; cmp <= x;) {
cmp = add(0,cmp,by);
floor = r;
r = add(0,r,1);
}
return floor;
}
نحن نستخدم الحجة الأولى من add وظيفة لأننا لا نستطيع للدلالة على نوع من المؤشرات دون استخدام * حرف إلا في وظيفة معلمة القوائم ، حيث الجملة type[] مطابق type* const.
FWIW, يمكنك بسهولة تنفيذ الضرب وظيفة باستخدام خدعة مماثلة لاستخدام 0x55555556 خدعة المقترحة من قبل AndreyT:
int mul(int const x, int const y) {
return sizeof(struct {
char const ignore[y];
}[x]);
}
من الممكن بسهولة على setun computer .
لتقسيم عدد صحيح بمقدار 3، Shift مباشرة بمكان .
أنا لست متأكدا مما إذا كان من الممكن بدقة تنفيذ مترجم C مطابق على مثل هذه المنصة رغم ذلك.قد يتعين علينا أن تمتد القواعد قليلا، مثل تفسير "8 بت لا يقل عن 8 بت" ك "قادرة على عقد أعداد صحيحة على الأقل من -128 إلى + 127".
لأنه من Oracle، ماذا عن جدول بحث للإجابات المحسوبة مسبقا.:-D
ها هو الحل:
public static int div_by_3(long a) {
a <<= 30;
for(int i = 2; i <= 32 ; i <<= 1) {
a = add(a, a >> i);
}
return (int) (a >> 32);
}
public static long add(long a, long b) {
long carry = (a & b) << 1;
long sum = (a ^ b);
return carry == 0 ? sum : add(carry, sum);
}
أولا ملاحظة أن
1/3 = 1/4 + 1/16 + 1/64 + ...
الآن بقية بسيط!
a/3 = a * 1/3
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...
الآن كل ما علينا فعله هو إضافة معا هذه بت تحول القيم!عفوا!لا يمكننا إضافة على الرغم من ذلك وبدلا من ذلك ، يجب أن يكتب إضافة وظيفة باستخدام بت الحكمة مشغلي!إذا كنت على دراية بت الحكمة مشغلي الحل يجب أن نظرة بسيطة إلى حد ما...ولكن فقط في حال كنت لا ، أنا سوف المشي من خلال مثال في نهاية المطاف.
شيء آخر هو أن نلاحظ أن أول أنا shift اليسار قبل 30!هذا هو للتأكد من أن الكسور لا تحصل على تقريب.
11 + 6
1011 + 0110
sum = 1011 ^ 0110 = 1101
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100
Now you recurse!
1101 + 0100
sum = 1101 ^ 0100 = 1001
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000
Again!
1001 + 1000
sum = 1001 ^ 1000 = 0001
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000
One last time!
0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17
carry = (0001 & 10000) << 1 = 0
Done!
انها تحمل ببساطة إلى أن تعلمت طفلا!
111
1011
+0110
-----
10001
هذا التنفيذ فشل لأننا لا يمكن إضافة جميع شروط المعادلة:
a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i
لنفترض reslut من div_by_3(a) = س ، ثم x <= floor(f(a, i)) < a / 3.عندما a = 3k, نحصل على إجابة خاطئة.
لتقسيم رقم 32 بت بمقدار 3، يمكن أن يتضاعفها من قبل GuidacodicetAchcode ثم خذ البتات 32 العلوي من نتيجة 64 بت.
الآن كل ما تبقى للقيام به هو تطبيق الضرب باستخدام عمليات البت وتغير ...
حل آخر.يجب أن يتعامل هذا مع جميع المخالفين (بما في ذلك INTS السلبي) باستثناء قيمة الحد الأدنى للمملكة المتحدة، والتي ستحتاج إلى التعامل معها كاستثناء مشفر بجد.هذا يقوم بشكل أساسي بالتقسيم بالطرح ولكن فقط باستخدام مشغلي البت (التحولات، XOR، وتكمل).لسرعة أسرع، يطرح 3 * (تقليل صلاحيات 2).في C #، فإنه ينفذ حوالي 444 من هذه divideby3 يدعو لكل مللي ثانية (2.2 ثانية مقابل 1،000،000 تقسيم)، لذلك ليس بطيئا بشكل مروع، ولكن لا يوجد مكان بالقرب من السرعة مثل x / 3 بسيطة.بالمقارنة، يكون حل Coodey لطيفة حوالي 5 مرات أسرع من هذا.
giveacodicetagpre.هذا هو C # لأن هذا ما كان لدي مفيد، لكن الاختلافات من C يجب أن تكون بسيطة.
انها حقا سهلة للغاية.
if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;
(لقد حذفت بالطبع بعض البرنامج من أجل الإيجاز.) إذا سئم المبرمج من كتابة هذا كله ، فأنا متأكد من أنه يمكنه كتابة برنامج منفصل لإنشائه له.أنا يحدث ليكون على بينة من عامل معين, /, ، من شأنه أن يبسط وظيفته بشكل كبير.
باستخدام عدادات هو الحل الأساسي:
giveacodicetagpre.من السهل أيضا إجراء وظيفة معامل، والتحقق من التعليقات.
هذه واحدة هي خوارزمية القسم الكلاسيكية في القاعدة 2:
giveacodicetagpre.كتابة البرنامج في باسكال واستخدام DIV المشغل.
منذ أن تم وضع علامة على السؤال c, ، ربما يمكنك كتابة دالة في باسكال وتسميتها من برنامج سي الخاص بك;طريقة القيام بذلك خاصة بالنظام.
ولكن هنا مثال يعمل على نظام أوبونتو بلدي مع باسكال الحرة fp-compiler حزمة تثبيت.(أفعل هذا بدافع العناد المطلق في غير محله;أنا لا أدعي أن هذا مفيد.)
divide_by_3.pas :
unit Divide_By_3;
interface
function div_by_3(n: integer): integer; cdecl; export;
implementation
function div_by_3(n: integer): integer; cdecl;
begin
div_by_3 := n div 3;
end;
end.
main.c :
#include <stdio.h>
#include <stdlib.h>
extern int div_by_3(int n);
int main(void) {
int n;
fputs("Enter a number: ", stdout);
fflush(stdout);
scanf("%d", &n);
printf("%d / 3 = %d\n", n, div_by_3(n));
return 0;
}
لبناء:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
تنفيذ العينة:
$ ./main
Enter a number: 100
100 / 3 = 33
لم تحقق عرضا إذا تم نشر هذه الإجابة بالفعل.إذا كان البرنامج بحاجة إلى تمديده للأرقام العائمة، فيمكن ضرب الأرقام بنسبة 10 * عدد الدقة المطلوب ثم يمكن تطبيق التعليمات البرمجية التالية مرة أخرى.
giveacodicetagpre.يجب أن يعمل هذا لأي مقسم، وليس فقط ثلاثة.حاليا فقط لعملية غير موقعة، ولكن تمديدها للتوقيع لا ينبغي أن يكون ذلك صعبا.
giveacodicetagpre.سيكون من الغش لاستخدام / المشغل "وراء الكواليس" باستخدام eval وسلسلة سلسلة?
على سبيل المثال ، في جافاكريبت ، يمكنك القيام به
function div3 (n) {
var div = String.fromCharCode(47);
return eval([n, div, 3].join(""));
}
أولا أن جئت مع.
irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub(' ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222
تحرير: آسف ، لم ألاحظ العلامة C.ولكن يمكنك استخدام فكرة تنسيق السلسلة ، على ما أعتقد...
يقوم البرنامج النصي التالي بإنشاء برنامج ج يحل المشكلة دون استخدام عوامل التشغيل * / + - %:
#!/usr/bin/env python3
print('''#include <stdint.h>
#include <stdio.h>
const int32_t div_by_3(const int32_t input)
{
''')
for i in range(-2**31, 2**31):
print(' if(input == %d) return %d;' % (i, i / 3))
print(r'''
return 42; // impossible
}
int main()
{
const int32_t number = 8;
printf("%d / 3 = %d\n", number, div_by_3(number));
}
''')
باستخدام هاكر البهجة ماجيك عدد حاسبة
int divideByThree(int num)
{
return (fma(num, 1431655766, 0) >> 32);
}
أين فما هي وظيفة مكتبة قياسية محددة في math.h رأس.
ماذا عن هذا النهج (C #)؟
giveacodicetagpre.أعتقد أن الإجابة الصحيحة هي:
لماذا لا أستخدم مشغل أساسي للقيام بعملية أساسية؟
الحل باستخدام وظيفة مكتبة FMA ()الرقم الإيجابي:
giveacodicetagpre.href="https://stackoverflow.com/a/11757290/981787"> شاهد إجابتي الأخرى .
استخدم cblas ، المدرجةكجزء من الإسراع في نظام التشغيل OS X.
giveacodicetagpre.أولا:
x/3 = (x/4) / (1-1/4)
ثم معرفة كيفية حل س / (1-ص):
x/(1-1/y)
= x * (1+y) / (1-y^2)
= x * (1+y) * (1+y^2) / (1-y^4)
= ...
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i)) / (1-y^(2^(i+i))
= x * (1+y) * (1+y^2) * (1+y^4) * ... * (1+y^(2^i))
مع ص = 1/4:
int div3(int x) {
x <<= 6; // need more precise
x += x>>2; // x = x * (1+(1/2)^2)
x += x>>4; // x = x * (1+(1/2)^4)
x += x>>8; // x = x * (1+(1/2)^8)
x += x>>16; // x = x * (1+(1/2)^16)
return (x+1)>>8; // as (1-(1/2)^32) very near 1,
// we plus 1 instead of div (1-(1/2)^32)
}
على الرغم من أنه يستخدم +, ، ولكن شخص ما ينفذ بالفعل إضافة من قبل أوب بيتويز.
حسنا، أعتقد أننا جميعا نتفق جميعا على أن هذه ليست مشكلة عالمية حقيقية.لذلك فقط للمتعة، إليك كيفية القيام بذلك مع ADA و Multitheading:
giveacodicetagpre.