2012-02-12 18 views
5

कुछ दिन पहले मैंने क्वालकॉम के साथ एक साक्षात्कार किया था। मैं एक सवाल पर अटक गया था, सवाल आप बहुत सरल लग रहे थे, लेकिन न तो मुझे और न ही साक्षात्कारकर्ता मेरे उत्तरों से संतुष्ट थे, अगर कोई इस समस्या का कोई अच्छा समाधान प्रदान कर सकता है।दो संख्याओं का गुणा

सवाल यह है:

गुणा 2 किसी भी छोरों और परिवर्धन और निश्चित रूप से कोई गुणा और भाग का उपयोग किए बिना नंबर।

जो मैंने जवाब दिया करने के लिए: प्रत्यावर्तन

उन्होंने कहा कि बहुत निचले स्तर पर कुछ और।

जिस पर मेरे दिमाग में वास्तविक विचार थोड़ा सा स्थानांतरित हो रहा था, लेकिन थोड़ा स्थानांतरण केवल संख्या 2 की शक्ति से गुणा करेगा और अन्य संख्याओं के लिए हमें अंततः एक अतिरिक्त करना होगा।

उदाहरण के लिए: (7 ~~ 111 की बाइनरी) < 2 + 10 < < 1 + 10 40 + 20 + 10 = 70

लेकिन फिर इसके अलावा: 10 * 7 के रूप में किया जा सकता है अनुमति नहीं थी।

इस मुद्दे पर कोई विचार।

+0

गुणा है अनुमति? – Kos

+2

क्या '*' ऑपरेटर की अनुमति है? – ouah

+0

hehecourse नहीं ... कोई गुणा नहीं "*" और कोई विभाजन नहीं। –

उत्तर

0

गुणा तालिकाओं के बारे में कैसे?

+1

क्या आप कृपया विस्तृत कर सकते हैं ... –

+0

तकनीकी रूप से यह सबसे आसान, सबसे तेज़ कार्यान्वयन है लेकिन स्मृति का उपभोग करता है। पूर्व में 4 बिट x 4 बिट में अधिकतम 8 बिट डेटा आउटपुट हो सकता है जिसे मल्टीप्लेक्सर द्वारा महसूस किया जा सकता है! हालांकि बड़ी संख्या के लिए यह विधि खराब है। अभी भी समस्या को धड़कता है -_- – Akshay

+0

क्या आप उदाहरण दे सकते हैं कि आप क्या कह रहे हैं .. 'गुणा तालिकाओं' –

2

शायद आप अतिरिक्त ऑपरेटर के प्रतिस्थापन के रूप में बिटवाई ऑपरेशंस का उपयोग करके पुनः जोड़ सकते हैं। देखें: Adding Two Numbers With Bitwise and Shift Operators

0

अतिरिक्त उपयोग किए बिना रूसी किसान गुणा के बारे में क्या? क्या केवल एक, या, एक्सओआर और नहीं का उपयोग करके अतिरिक्त अनुकरण करने के लिए कोई आसान तरीका है (कुछ लाइनें, कोई लूप नहीं)?

+0

एलेक्स रेनॉल्ड्स के पास जो मैं खोज रहा था। ठंडा। –

0

आप बिट्स ऑपरेटरों द्वारा अतिरिक्त कार्यान्वित कर सकते हैं। लेकिन फिर भी, अगर आप लूप से बचना चाहते हैं, तो आपको बहुत सारे कोड लिखना चाहिए। (मैं अंकगणितीय ऑपरेटर के बिना गुणा लागू करने के लिए प्रयोग किया जाता है, लेकिन मैं पाश का उपयोग करें, सूचकांक स्थानांतरण जब तक यह शून्य हो गया। यह आपकी मदद कर सकते हैं, मुझे बताओ, और मैं फ़ाइल खोज करेंगे)

1

आप पहले से अपनी समस्याओं को अलग कर सकते जोड़ के कार्यान्वयन और फिर अतिरिक्त के आधार पर गुणा लागू करना।

इसके अलावा के लिए, को लागू है कि वे क्या सी बिटवाइज़ ऑपरेटर्स का उपयोग कर गेट स्तर पर प्रोसेसर पर कार्य करें:,

http://en.wikipedia.org/wiki/Full_adder

फिर गुणन के लिए

इसके अलावा आप कार्यान्वित के साथ, goto बयानों का उपयोग करें और इसलिए लेबल कोई लूप स्टेटमेंट नहीं (for, while और do पुनरावृत्ति विवरण) का उपयोग किया जाएगा।

6

यहां लुकअप, जोड़ और स्थानांतरण का उपयोग करके एक समाधान है। लुकअप को गुणा की आवश्यकता नहीं है क्योंकि यह अन्य सरणी के पॉइंटर्स की एक सरणी है - इसलिए सही सरणी खोजने के लिए अतिरिक्त आवश्यकता है। फिर दूसरे मान का उपयोग करके आप पॉइंटर अंकगणित दोहरा सकते हैं और लुकअप परिणाम प्राप्त कर सकते हैं।

#include <stdio.h> 
#include <stdlib.h> 

int main(int argc, char **argv) 
{ 
    /* Note:As this is an array of pointers to an array of values, addition is 
    only required for the lookup. 

    i.e. 

    First part: lookup + a value -> A pointer to an array 
    Second part - Add a value to the pointer to above pointer to get the value 
    */ 
    unsigned char lookup[16][16] = { 
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, 
    { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 }, 
    { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45 }, 
    { 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 }, 
    { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75 }, 
    { 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90 }, 
    { 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105 }, 
    { 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120 }, 
    { 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135 }, 
    { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 }, 
    { 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165 }, 
    { 0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180 }, 
    { 0, 13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195 }, 
    { 0, 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210 }, 
    { 0, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225 } 
    }; 
    unsigned short answer, mult; 
    unsigned char x, y, a, b; 

    x = (unsigned char)atoi(argv[1]); 
    y = (unsigned char)atoi(argv[2]); 
    printf("Multiple %d by %d\n", x, y); 

    answer = 0; 
    /* First nibble of x, First nibble of y */ 
    a = x & 0xf; 
    b = y & 0xf; 
    mult = lookup[a][b]; 
    answer += mult; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* First nibble of x, Second nibble of y */ 
    a = x & 0xf; 
    b = (y & 0xf0) >> 4; 
    mult = lookup[a][b]; 
    answer += mult << 4; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* Second nibble of x, First nibble of y */ 
    a = (x & 0xf0) >> 4; 
    b = y & 0xf; 
    mult = lookup[a][b]; 
    answer += mult << 4; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* Second nibble of x, Second nibble of y */ 
    a = (x & 0xf0) >> 4; 
    b = (y & 0xf0) >> 4; 
    mult = lookup[a][b]; 
    answer += mult << 8; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    return 0; 
} 
0

प्रश्न: किसी भी छोरों और परिवर्धन और निश्चित रूप से कोई गुणा और भाग का उपयोग किए बिना गुणा 2 संख्या।

गुणा को अतिरिक्तता के संदर्भ में परिभाषित किया गया है। गुणा के कार्यान्वयन में जोड़ना असंभव है।

मनमाने ढंग से सटीक संख्याओं को लूप/रिकर्सन के बिना गुणा नहीं किया जा सकता है।

निश्चित बिट-लम्बाई की दो संख्याओं के गुणा को तालिका लुकअप के माध्यम से कार्यान्वित किया जा सकता है। समस्या तालिका का आकार है। तालिका उत्पन्न करने के लिए अतिरिक्त आवश्यकता है।

उत्तर है: यह नहीं किया जा सकता है।

0

आप इसके बजाय लॉगरिदम और घटाव का उपयोग कर सकते हैं।

लॉग (एक * ख) = लॉग (क) + लॉग (ख)
ए + बी = - (- ab)
exp (लॉग (क)) = एक

round(exp(-(-log(a)-log(b)))) 
संबंधित मुद्दे